1182 부분 수열의 합

#include<iostream>
#include<vector>	
#include<string>
#include<algorithm>
using namespace std;
vector<int>arr;

int n, m,answer=0;

void pw(int i,int sum) {
	if (i == n) {
		if (sum == m) {
			answer++;
		}
		return;
	}
	pw(i+1, sum);
	pw(i + 1, sum + arr[i]);
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	cin >> n >> m;

	for (int i = 0;i < n;i++) {
		int c;
		cin >> c;
		arr.push_back(c);
	}
	pw(0, 0);

	if (m == 0) {
		answer--;//아무것도 안더한 경우의수 빼기
	}
	 
	cout << answer;
	return 0;
}

총 n개의 노드가 존재할 때, n번째 호출된 경우에만 정답을 확인한다. 뒤에 0을 더해주는 경우가 있을 수도 있고 모든 경우를 확인해주기 위함인듯.

재귀호출에서 pw(i+1,sum); pw(i+1,sum+arr[i]);

를 호출하는데 i번째 항을 더해준 경우와 더하지 않은 경우로 나뉘어 트리 형식으로 생각 가능하다.

 

for문으로 pw(0,0)부터 pw(n-1,0)까지 확인을 해야하나 싶었는데 재귀호출 과정에서 pw(i+1,sum);의 호출을 통해 모든 경우의 수를 확인 가능하여 필요하지 않다는 것을 알앗음..