부분수열의 합

백준 1182번: 부분수열의 합

아이디어

N개의 숫자 각각 포함시키거나 포함시키지 않는 경우를 모두 탐색한다. 2^N인데 N이 작아서 풀 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, S, CNT = 0;

void solve(int sum, int idx, vector<int>& v) {
    if (idx == N) {
        if (sum == S) {
            CNT++;
        }
        return;
    }
    solve(sum + v[idx], idx + 1, v);
    solve(sum, idx + 1, v);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<int> v;
    cin >> N >> S;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    solve(0, 0, v);
    if (S == 0) CNT--;
    cout << CNT;
        
    return 0;
}

여담

벡터를 전달할 때 &(참조자)로 전달하면 시간이 1/22로 줄어든다. 대박! 그냥 전달하면 벡터를 복사하는데 시간이 들기 때문이다.