[BOJ] 1182번 : 부분수열의 합

1. problem : 

https://www.acmicpc.net/problem/1182

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int N, S;
int numbers[20];
int ans = 0;

void findSubsequence(int index, int currentSum) {
	if (index == N) {
		if (currentSum == S) {
			ans++;
		}
		return;
	}
	findSubsequence(index + 1, currentSum + numbers[index]);
	findSubsequence(index + 1, currentSum);
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> S; 
	for (int i = 0; i < N; i++) cin >> numbers[i]; 
	findSubsequence(0, 0);
	if (S == 0) ans--; 

	cout << ans << '\n';
}

two pointer기법으로 풀려다가, 더해주는 과정에서 numbers [l]과 numbers [r]을 더하는 과정에서 중복이 일어나게 되어, 꼬였다. chatgpt4o한테 물어보니 backtracking으로 푼다고 한다. 기저사례를 설정하고, 재귀적으로 호출하는데, index를 더할 수도 있고 아닐 수도 있는 2가지의 경우의 수를 고려해서 답을 도출한다.