부분수열의 합 (feat. 백준, 1182번)

부분수열의 합
https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int N, S, arr[20], ans;
bool visit[20];
void dfs(register int idx, register int sum){
    if(idx > 0 && sum == S)
        ++ans;
    for(register int i = idx; i < N; ++i)
        if(!visit[i]){
            visit[i] = true;
            dfs(i + 1, sum + arr[i]);
            visit[i] = false;
        }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    ans = 0;
    cin >> N >> S;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n], visit[n] = false;
    dfs(0, 0);
    cout << ans;
    return 0;
}
// *&)*@*

 

 

1. N개의 배열과 값 S가 주어졌을때, 1개 ~ N개의 조합의 합이 S와 같은 경우의 총 개수를 구하는 문제입니다.
2. 순열과 조합은 dfs를 통해 간편하게 구할 수 있습니다.