[BOJ] 1182 부분수열의 합

부분 수열 합이 S가 되었다고 해도 끝까지 확인을 해보면 또 다시 S가 나올 수 있다. 

처음에 S가 0일 경우가 있을 수도 있다. 따라서 합을 레이어가 시작할 때 구한다. 

#include <iostream>
#define MAXN 20
using namespace std;

int N, S, cnt =0 ;
long long A[MAXN];

void input(){
    cin >> N >> S;
    int i = 0;
    while(i < N)
        cin >> A[i++];
}
void solve(long long sum , int index){
    sum += A[index];
    if(index >= N)
        return;

    if(sum == S )
        cnt++;

    solve( sum -A[index], index+1);

    solve(sum, index+1);


}
int main() {

    input();
    solve(0,0);

    cout << cnt << endl;
    return 0;
}

 

 

 

백준 1182번 부분집합의 합

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