[1182] 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

<문제>

항상 더하거나 유지하거나, 두가지로 분기된다.

s==0일때에는 공집합마저 하나로 카운트되므로, 이때에만 -1을 별도로 진행해주어야 한다.

2^20 == 100만정도이니, 단순히 완전탐색해줄 수 있다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, s, a[21];
int f(int d, int sum) {
    if (d == n) return sum == s;
    return f(d + 1, sum + a[d]) + f(d + 1, sum);
}
int main(void) {
    cin >> n >> s;
    int i;
    for (i = 0; i < n; i++) cin >> a[i];
    if (s == 0)
        cout << f(0, 0) - 1;
    else
        cout << f(0, 0);
    return 0;
}