백준 1182 부분수열의 합

sum은 인자로 전달해준다.

중간에 원소 몇 개로 합을 완성할 수도 있지만, 아래 코드에서 sum과 s가 같더라도 이후의 원소가 들어오는 것에 따라서 다시 sum과 s가 같아질 수 있다.

따라서 경우의 수를 (s==sum && i == n)과 (s != sum && i == n) 두 가지로 나누어서 풀어야 한다.

또한 합이 0이 입력되면, 아무것도 선택하지 않아도 0이 되므로, 공집합은 허용되지 않는다. 따라서 답을 출력할 때 1을 빼준다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n, s;
vector<int> v(20);
int ans;
 
void go(int i, int sum) {
    if (s == sum && i == n) {
        ans++;
        return;
    }
    if (s != sum && i == n) return ;
    go(i + 1, sum);
    go(i + 1, sum + v[i]);
}
 
int main(int argc, char* argv[]) {
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    go(0, 0);
    if (s == 0)ans--;
    cout << ans << '\n';
 
    return 0;
}