BOJ 1182 · 부분집합의 합

알고리즘 분류 : 브루트 포스  

재귀 함수를 이용하여 구현할 수 있는 문제다.

집합의 원소가 N 개 있을 때, 모든 부분집합의 개수는 2^N 개이다. N의 제한이 최대 20이므로, 가능한 경우의 수는 2^20 (약 100만)이다. 따라서 모든 부분 집합을 구한 후, 그 집합의 합이 S 인지 판별해보면 된다.

• 재귀 함수 종료 조건 : 인덱스가 범위를 벗어난 경우 (index >= N)
• 정답을 찾은 경우 : 부분집합의 총합이 S인 경우 (sum == S)
• 원소를 포함하는 경우 : solve(index+1, sum+a[index])
• 원소를 포함하지 않는 경우 : solve(index+1, sum)
• 공집합을 포함하지 않으므로, S가 0인 경우 1개를 정답에서 빼야 한다.

---

C++ 소스코드

#include <cstdio>

int n, s, ans;
int a[20];

void solve(int index, int sums) {
    if (index >= n) {
        if (sums == s) ans++;
        return;
    }
    solve(index+1, sums+a[index]);
    solve(index+1, sums);
}

int main() {
    scanf("%d %d", &n, &s);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    solve(0, 0);
    if (s == 0) ans--;
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n, s = map(int, input().split())
a = list(map(int, input().split()))
ans = 0

def solve(index, sums):
    global ans
    if index >= n:
        if sums == s:
            ans += 1
        return
    solve(index+1, sums+a[index])
    solve(index+1, sums)

solve(0, 0)
print(ans if s else ans-1)

---

참고

• 백준 온라인 저지 : BOJ 1182