[백준/C++] 1182번: 부분수열의 합 (DFS)

 

주의점 1) 연속된 수의 합을 찾는 것이 아니다.

ex) N=4, sum=0, arr=[100, 100, 100, -100]일 때, 연속된 수의 합이라면 답이 1개이다. 하지만 (100,-100)조합이 3번 가능하므로 답이 3개이다.

 

주의점 2) 부분집합의 합이 아니니 중복이 포함된다.

ex) N=4, sum=1, arr=[1, -1, 1, 2]일 때, 부분집합의 합이라면 [1], [-1, 2], [1, -1, 1]로 답이 2개이다. 하지만 첫번째 1과 세번째 1은 다른 1로 처리해야한다. 그래서 [1], [1], [-1, 2], [1, -1, 1]로 답이 4개이다. 

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, sum;
vector<int> arr;

int cnt = 0;
void solve(int idx, int tmp) {

	if (idx == N) return;
	if (tmp + arr[idx] == sum) cnt++;

	solve(idx + 1, tmp);
	solve(idx + 1, tmp + arr[idx]);
}

int main() {
	
	cin >> N >> sum;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	solve(0, 0);
	cout << cnt;

	return 0;
}