BOJ 1182 부분수열의 합

BOJ 1182 부분수열의 합

문제링크 : https://www.acmicpc.net/problem/1182

요약

무작위의 n의 크기의 수열이 주어질때 그 수열의 숫자로 만들수 있는 부분집합의 합이 입력받은 s가 되는 경우의 수를 구하는 문제

풀이

n의 크기가 20이므로 부분집합의 최대크가는 2^20이 되므로 완전탐색을 사용하여도 된다. 재귀함수를 이용하여 모든 부분집합의 경우의 수를 확인하고 s가 되는 경우의 수를 세주었다.

코드

#include <iostream>
using namespace std;
int n, s, ans, arr[20];
void solve(int idx, int sum) {
	if (idx >= n) {
		if (sum == s) ans++;
		return;
	}
	solve(idx + 1, sum + arr[idx]);
	solve(idx + 1, sum);
}
int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	solve(0, 0);
	if (s == 0) ans--;
    cout << ans << "\n";
	return 0;
}