백준) 1182 부분집합의 합

부분집합의 합 

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

각 원소들을 넣던지, 빼던지 해서 2가지 경우씩 발생한다. 따라서 모든 원소와 관련해 부분집합은 2^n개 생긴다.

원소가 최대 20개 이므로 브루트포스로 백만번의 연산으로 답을 얻을 수 있다.

하지만 분명 쓸따리 없는 연산도 존재한다.

가령 예를 들어 {0, 1, 2, 3, 4, 5}의 집합에서, S=6을 만드는 부분집합을 찾기위해, 첫 원소부터 넣을 것인지를 고려하다가,

{0, 1, 2, 3}까지 더해서 이미 6을 만들었는데, 나머지 {4, 5}를 넣을지 뺄지 고민할 필요가 없는 것이다.

하지만 이러한 가지치기(prunning)는 뒤의 수가 앞의 수보다 크다는 가정하에 진행되므로, 배열의 정렬이 필요하다.

정렬 이후엔 재귀안에 가지치는 코드를 넣어주자.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n[20], N, S, ans;
 
void dfs(int cur_sum, int cnt, int idx) {
    if (idx >= N)
        return;
 
    if (cur_sum + n[idx] > S) {
        if (n[idx] >= 0)
            return;
    }
 
    if (cur_sum + n[idx] == S)
        ans++;
 
    dfs(cur_sum + n[idx], cnt + 1, idx + 1);
    dfs(cur_sum, cnt, idx + 1);
}
 
int main() {
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; ++i)
        scanf("%d", &n[i]);
 
    sort(n, n + N);
    dfs(0, 0, 0);
 
    printf("%d", ans);
 
    return 0;
}