부분 수열을 더해서 주어진 s가 되는 경우의 수를 구하는 문제.
dfs로 전수조사 하는 방식으로 해결 할 수 있다.
각 노드를 더할지 말지 결정하는 방식을 가진 dfs를 사용하면, 부분 수열을 쉽게 만들 수 있다.
[3,5,-2,-3] 의 경우, 부분 수열의 합으로 0을 만든다고 하면.
이번 풀이에서 가장 중요한 부분은
dfs(i+1, sum) //현재 탐색한 노드의 수를 더하지 않고 다음 노드 탐색
dfs(i+1, sum + v[i]) //현재 탐색한 노드의 수를 더하고 다음 노드 탐색
현재 탐색중인 노드의 값을 선택할지 말지 결정하는 코드이다.
#include <iostream>
#include <vector>
using namespace std;
int n, s;
vector<int> v;
int cnt = 0;
void dfs(int i, int sum) {
if (i == n) return;
if (sum + v[i] == s) cnt++;
dfs(i + 1, sum);
dfs(i + 1, sum + v[i]);
}
int main() {
cin >> n >> s;
int a;
for (int i = 0; i < n; i++) {
cin >> a;
v.push_back(a);
}
dfs(0, 0);
cout << cnt;
}