본문 바로가기

Programming/BOJ

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)




참고



태그