[백준] 1182 부분 수열의 합

부분 수열을 더하면서 입력한 값과 같게 되는 경우의 수를 구하는 문제인데

 

백트래킹의 기본적인 문제인데 출력값이 자꾸 하나씩 더 나와서 당황했다.

 

원인은 원하는 값이 0인 경우 count값이 0부터 시작하여 값이 한개 더 추가된다는 것 이였다.

그래서 조건문에서 count가 1부터 통과되록 조건을 추가 시켜서 해결하였다.

 

#include <bits/stdc++.h>

using namespace std;

vector<int> input1182(21,0);
vector<bool> check1182(21,false);
int N1182,S1182;
int result1182 = 0;

void backback1182(int count, int pos, int sum){
    
    if(sum == S1182 && count > 0)
        result1182 ++;
    
    if( count == N1182)
        return;
    
    
    for(int i=pos; i<=N1182; ++i){
        if(!check1182[i]){
            check1182[i] = true;
            backback1182(count+1, i+1, sum + input1182[i]);
            check1182[i] = false;
        }
    }
    
}

void subSequence1182(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N1182 >> S1182;
    
    for(int i=1;i<=N1182;i++)
        cin>>input1182[i];
    
    backback1182(0, 1, 0);
    
    cout<<result1182<<"\n";
}

 

□ 유용한 반례

5 0
0 0 0 0 0
ANS: 31

5, 10, 10, 2 ,1