[BOJ 1182 // C++] 부분수열의 합

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1182번 문제인 부분수열의 합이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

N의 최댓값이 20이므로, 모든 경우의 수는 많아봐야 2^20(대략 100만)가지가 된다는 것을 알 수 있다.

따라서, 단순히 모든 경우의 수를 탐색하는 것으로 이 문제는 해결할 수 있다.

같은 경우를 중복을 피해 계수하자.

 

아래 제출 코드에서 주석이 달린 부분이 있는 것은, 총합이 0인 경우 초기값때문에 코드상 경우의 수가 하나 더 세어지기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[20];
int currentsum = 0;
int N, S, ans = 0;

void func(int current) {
    if (currentsum == S) ans++;
    for (int i = current;i < N;i++) {
        currentsum += arr[i];
        func(i + 1);
        currentsum -= arr[i];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S;
    for (int i = 0;i < N;i++) {
        cin >> arr[i];
    }

    if (S == 0) ans--; // currentsum의 초기값 0과 겹쳐서 한번 더 세지므로
    func(0);

    cout << ans;
}