백준 1182 : 부분수열의 합

문제 링크입니다 https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

재귀 함수를 이용해 모든 경우를 탐색하는 방식으로 문제를 해결했습니다. 합이 0인 부분집합을 찾을 때, 크기가 양수인 부분집합을 찾아야 한다는 사실을 주의해서 풀어야 했습니다. 자세한 설명은 주석을 참고해주세요.

 

 

[소스코드]

 

#include<cstdio>
 
int n, s, num[20], ret;
 
// 부분집합의 모든 경우를 보기 위해 고를지 말지 결정하는 i와
// 현재까지 고른 원소들의 합을 나타내는 sum을 인자로 받아
// 정답인 경우를 찾으면 ret를 증가시키는 함수
void solve(int i, int sum) {
 
    // 모든 원소에 대해서 고르거나 고르지 않았으면
    if (i == n){
        // 고른 원소들의 합이 s이면
        if (sum == s) {
            ret++;    // 정답인 경우이므로 ret 증가
        }
 
        // 고른 원소들의 합이 s이든 아니든 return
        return;
    }
    solve(i + 1, sum + num[i]); // 현재 원소를 고르고 다음으로 갑니다
    solve(i + 1, sum);          // 현재 원소를 고르지 않고 다음으로 갑니다
}
 
int main(void) {
 
    scanf("%d%d", &n, &s);
    for (int i = 0; i < n; i++)
        scanf("%d", &num[i]);
 
    solve(0, 0);
 
    // s가 0일 때는 아무것도 고르지 않은 경우가 답에 포함되어 있습니다
    // 하지만 문제에서 "크기가 양수인 부분집합 중에서"라 했기 때문에 -1을 해줍니다
    if (s == 0) ret -= 1;
 
    printf("%d", ret);
    return 0;
}