[C++] 백준 1182번 부분수열의 합

부분수열의 합이 S가 되는 경우의 개수를 찾는 문제입니다.

재귀함수를 통해서 인덱스 1~N까지 차례대로
현재 인덱스의 수를 더하는 경우와
현재 인덱스의 수를 패스하는 경우에 대해서
계산을 하며, 만약 S가 되면 카운트를 해줍니다.

 

#include <iostream>
using namespace std;

int N, S;
int arr[30];
int result = 0;

void solve(int index, int sum)
{
	sum += arr[index];

	if (index >= N) {
		return;
	}
	if (sum == S) {
		result++;
	}
	
	solve(index + 1, sum - arr[index]);
	solve(index + 1, sum);
}

int main(int argc, char *argv[])
{
	cin >> N >> S;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	solve(0, 0);

	cout << result << endl;
	return 0;
}