<Baekjoon> #1182 DFS_부분 수열의 합 c++

#1182 부분수열의 합

합이 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;
}