[C/C++] 백준 1182번 부분수열의 합 - 참고

 

 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> num;

int N, S; // 전역 변수
int cnt = 0;

void DFS(int index, int n) {


	if (index == N) { 
		return;
	}

	if (num[index] + n == S){ // 부분수열의 합이 S와 같을 경우 개수 추가
		cnt++;
	}

	DFS(index + 1, n); // 왼쪽 경우 : 현재 수(num[index])를 더하지 않는다.
	DFS(index + 1, num[index] + n); // 오른쪽 경우 : 현재 수(num[index])를 더한다.

}

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

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

	DFS(0, 0); // 인덱스 0과 초기값 0으로 시작

	cout << cnt;

	return 0;
}