[BOJ] 백준 1182 부분수열의 합

출처: https://www.acmicpc.net/problem/1182

 Input 

5 0

-7 -3 -2 5 8

 

 Output 

 1

 

N이 크지 않은 숫자이므로 부분 수열의 크기를 줄여가며

모든 부분 수열의 합을 구한 후, S와 같은지 확인합니다.

---

#include <iostream>
using namespace std;
 
int N, S, result;
int arr[20];
 
void solve(int idx, int sum){
    sum += arr[idx];
 
    if (idx >= N) return;
    if (sum == S) result++;
 
    solve(idx + 1, sum);
    solve(idx + 1, sum - arr[idx]);
}
 
int main(void) {
    
    cin >> N >> S;
 
    for(int i=0; i<N; i++){    
        cin >> arr[i];
    }
 
    solve(0, 0);
    
    cout << result << endl;
}