[백준] 백트래킹 - 1182. 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

예제 입력1

5 0
-7 -3 -2 5 8

 

예제 출력1

1

 

생각

이 문제의 경우는 n이 20까지이므로 재귀함수로 풀면 될 것 같았다. 

 

재귀호출되는 과정을 구하면 다음과 같다. 

인덱스를 증가시키면서, 해당 원소를 sum에 더하거나 혹은 더하지 않거나 이므로 호출할때마다 2배씩 증가한다. 

 

find(0, 0)

1) 첫번째 정수인 -7을 더하거나 더하지 않거나

-> find(1, -7) , find(1, 0)

2) 두번째 정수인 -3을 더하거나 더하지 않거나

-> find(2, -10), find(2, -7) , find(2, -3), find(2, 0)

3) 세번째 정수인 -2를 더하거나 더하지 않거나

-> find(3, -12), find(3, -10) / find(3, -9), find(3, -7),

find(3, -5), find(3, -3) / find(3,  -2), find(3, 0)

4) 네번째 정수인 -5를 더하거나 더하지 않거나

-> find(4, -7), find(4, -12), find(4, -5), find(4, -10) / find(4, -4),  find(4, -9), find(4, -5), find(4, -7),

find(4, 0), find(4, -5), find(4, 2), find(4, -3)/ find(4, 3), find(4, -2), find(4,5), find(4, 0)

5) 다섯번째 정수인 8을 더하거나 더하지 않거나

-> find(5, -1), find(5, -7), find(5, 4), find(5, -12), find(5, 3), find(5, -5), find(5, -2), find(5, -10) / find(5, 4), find(5, -4), find(5, -1),

find(5, -9), find(5, 3), find(5, -5), find(5, 1), find(5, -7),

find(5, 8), find(5, 0), find(5, 3), find(5, -5), find(5, 10), find(5, 2), find(5, 5), find(5, -2) / find(5, 11), find(5, 3), find(5, 6), find(5, -2), find(5, 13), find(5, 5), find(5, 5), find(5, 0)

 

작성한 코드

#include <iostream>

using namespace std;

int n,s;
int arr[21];
int cnt=0;
void find(int index, int sum){
    if(n==index){
        if(sum==s){
            cnt ++;
        }
        return;
    }
    find(index+1, sum+arr[index]); 
    find(index+1, sum);
}
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> s;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    find(0, 0);
    if(s==0){ //s가 0일 경우, 공집합에 대해 cnt값이 1이 추가되기때문에 빼줘야한다.
        cnt += -1;
    }
    cout << cnt << "\n";
    return 0;
}