#1182번 부분수열의 합 (C++)

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

1182번: 부분수열의 합

전형적인 백 트래킹 문제로, 자세한 해설은 해설하겠다.

한 가지 눈 여겨 볼 점은 'if(s==0) ans-=1' 부분인데, 

문제에서 크기가 양 수인 부분 수열, 즉, 최소 1개 이상의 원소를 갖는 부분 집합을 가져야 한다는 것을 언급했다.

아무것도 집합을 만들지 않으면 자동으로 0이 나오는데, 만약 s=0인 경우 이 상황을 고려해서 -1을 해줘야한다.

 

#include <iostream>
using namespace std;

int n=0, s=0, ans = 0;
int v[21];
void dfs(int index, int sum){
    if(index==n){
        if(sum==s) ans++;
        return;
    }
    dfs(index+1,sum+v[index]);
    dfs(index+1,sum);
}

int main(void) {
    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    dfs(0,0);
    if(s==0) ans-=1;
    cout << ans << "\n";
   return 0;
}