백준 부분수열의 합 1182 C++

1182: 부분수열의 합

부분 수열을 더해서 주어진 s가 되는 경우의 수를 구하는 문제.

dfs로 전수조사 하는 방식으로 해결 할 수 있다.

각 노드를 더할지 말지 결정하는 방식을 가진 dfs를 사용하면, 부분 수열을 쉽게 만들 수 있다.

[3,5,-2,-3] 의 경우, 부분 수열의 합으로 0을 만든다고 하면.

• sum이라는 변수에 3을 더한 뒤, 5와 -2를 빼고, -3을 더하면 합이 0이 된다.
• sum이라는 변수에 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;
}