합이 s가 되는 부분 수열을 구하는 문제는 dfs를 이용하여 간단하게 풀 수 있다.
예를 들어 {-7, -3, -2, 5, 8}
의 수열이 주어졌을 때, 처음 합 sum=0
에서 ⓐ-7
을 더하는 것과 ⓑ더하지 않는 부분으로 나누고 ⓐ-7
을 더한 곳에서 ⓒ-3
을 더하는 부분과 ⓓ더하지 않는 부분, ⓑ-7
을 더하지 않은 곳에서 ⓔ-3
을 더하는 부분과 ⓕ더하지 않는 부분으로 나누어 더해간다.
dfs(level + 1, sum + set[level]);
//왼쪽 자식으로 내려가는 부분
dfs(level + 1, sum);
//오른쪽 자식으로 내려가는 부분
소스코드
#include <iostream> #include <vector> using namespace std; int n, s; int ans = 0; vector<int> set; void dfs(int level, int sum) { if (level == n) return; if (sum + set[level] == s) ans++; dfs(level + 1, sum + set[level]); dfs(level + 1, sum); } int main() { cin >> n >> s; set = vector<int>(n); for (int i = 0; i < n; i++) cin >> set[i]; dfs(0, 0); cout << ans << endl; return 0; }