(C++) 백준 1182번 - 부분수열의 합

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

1182번: 부분수열의 합

풀이

백트래킹을 활용하여 풀이하였다.

부분수열에 숫자 하나를 포함하거나 포함하지 않거나 하는 경우를 모두 시도하여 조건에 맞는 경우를 카운트하는 식으로 풀이하였다. 

#include <iostream>

using namespace std;

int n, s, tmp, size, cnt;
int num[20];
int used[20];

void subseqadd(int index, int sum){
    if(index == n){ // base condition
        if(sum == s) cnt++;
        return;
    }
    subseqadd(index+1, sum); // 자기 자신을 부분수열에 미포함
    subseqadd(index+1, sum+num[index]);  // 자기 자신을 부분수열에 포함 
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n >> s;

    for(int i = 0; i < n; i++){
        cin >> tmp;
        num[i] = tmp;
    }
    subseqadd(0, 0);
    // s의 값이 0이라서 부분수열에 아무것도 들어있지 않을 때도 +1 되는 것을 제거하기 위함
    if(s == 0) cnt--; 
    cout << cnt;
}