[BOJ] 1182번: 부분집합의 합

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

모든 경우를 다 탐색하면 된다. 재귀 호출을 통해 풀 수도 있고 n이 20으로 작기 때문에 비트마스크를 이용해서 해결할 수 있다.

재귀 호출을 통해 문제를 푸는 경우 -> 현재 이 인덱스의 값을 더하거나 안 더하거나(인덱스만 증가시키거나)로 전체를 탐색할 수 있다. 정말 뻘짓을 많이 해서 친구의 도움을 많이 받았는데 연습 밖에는 답이 없는 듯하다.

소스코드

비트 마스크

#include <cstdio>
 
int main()
{
    int N, S, arr[20], count = 0;
    scanf("%d%d", &N, &S);
    for (int i = 0; i < N; ++i) scanf("%d", arr + i);
    for (int i = 1; i < (1 << N); ++i) {
        int sum = 0;
        for (int j = 0; j < N; ++j) 
            if (i & (1 << j)) sum += arr[j];
        if (sum == S) ++count;
    }
    printf("%d", count);
    return 0;
}

재귀 호출

S = 0일때 -1을 해주는 이유는 search(0, 0)을 호출하면 search(0, N)이 무조건 생긴다. 즉 공집합이기 때문에 처리를 해준 것이다.

#include <cstdio>
 
int N, S, A[21];
int cnt;
 
void search(int sum, int idx)
{
    if (idx == N) {
        if (sum == S) ++cnt;
        return;
    }
    search(sum + A[idx], idx + 1);
    search(sum, idx + 1);
}
 
int main()
{
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
    search(0, 0);
    printf("%d\n", (S == 0) ? cnt - 1 : cnt);
    return 0;
}