[C++]BJO 1882 : 부분수열의 합

문제

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

 

 

 

 

풀이

백트래킹을 이용해 푼다.

arr[]에 수열을 입력받고, used[]에 부분수열에 포함시킬 원소들을 표시해가며 표시한 원소의 합이 m이 될 때마다 카운트한다.

 

이때 부분수열이기 때문에, 숫자들간의 순서는 유지되어야 한다. 즉 각 부분수열 원소의 index는 뒤집히면 안된다.

 

 

코드

#include <iostream>
using namespace std;

int n,m, ans;
int arr[21];
int used[21];

void solve(int idx){

    int cnt = 0, num = 0;
    for(int i=1; i<=n; i++){
        if(used[i] == 1) {
            num++; // 공집합 제외 위함
            cnt += arr[i];
        }
    }
    
    if(cnt == m && num!=0) ans++;
    
    for(int i= 1; i<=n; i++){
        if(used[i] == 0 && idx <= i){
            used[i] = 1;
            solve(i);
            used[i] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> arr[i];
    
    solve(1);
    cout << ans << "\n";
    return 0;
}