백준 1182 - 부분수열의 합 - 브루트포스 , not 투 포인터

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

1182번: 부분수열의 합

부분수열이라는 이름에 걸맞게 투 포인터 알고리즘일 거라고 생각해서 풀이했으나, 

문제점을 발견했다. 

 

그 사례는 다음과 같다. 

5 3
1 1 1 1 1

 

이 경우 답은 5Combination(3) = 10인데도 답이 5가 나오는 문제였다.

생각해본 결과 이건 앞으로만 가면서 세기 때문에 중복된 숫자가 있을 경우 각각의 조합의 경우의 수를 찾기가 어렵다는 판단이 들었다.

 

따라서 N <= 20 이므로, 브루트포스로 찾는 것을 결심했다.

그러고나면 이제 어떤 인덱스를 뽑아서 합을 계산할지만 정하면되는 백트레킹 문제가 된다.

 

 

c++ 로 구현한 알고리즘은 다음과 같다. 

#include <iostream>
#include <algorithm>
using namespace std;
#define FAST std::ios::sync_with_stdio(0); std::cin.tie(0);
#define INF 2147483647
long long N, S;
long long nums[20] = {0,};
long long psum[20] = {0,};
long long counts = 0;

int selected[21] = {0,};
void dfs(int idx, int depth, int sum){
    // cout << "sum : " << sum << "\n";
    if(sum == S)
        counts++;
    if(depth == N){
        return;
    }

    for(int i = idx+1; i < N; i++ ){
        if(selected[i] == 0){
            selected[i] = 1;
            dfs(i, depth + 1, sum + nums[i]);
            selected[i] = 0;
        }
        
    }

}
int main() {
    cin >> N >> S;
    for(int i = 0; i < N; i++){
        cin >> nums[i];
        if(i == 0)
            psum[i] = nums[i];
        else
            psum[i] += psum[i-1];
    }
    for(int i = 0; i < N; i++){
        selected[i] = 1;
        dfs(i, 0, nums[i]);
        selected[i] = 0;
    }
    cout << counts;
}