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

문제

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

 

문제 내용

N개의 정수로 이루어진 수열의, 크기가 양수인 부분집합 중에 합이 S인 경우의 수를 구하면 된다.

 

문제 풀이

모든 원소는 2가지로 구분된다.

부분수열에 포함되거나, 포함되지 않거나.

각 원소에 대해 포함된 경우와 포함되지 않는 경우를 계산해보면 된다.

단, 합이 0일 때는 모든 원소를 포함시키지 않는 경우(공집합)도 포함되므로, 개수에서 -1을 해줘야 한다.

 

코드

#include <iostream>

using namespace std;

int arr[20];
int n, s;
int cnt = 0;

void back(int current, int ssum) {
    if (current == n) {
        if (ssum == s) {
            cnt++;
        }
        return;
    }

    back(current + 1, ssum);                // arr[current]를 더하지 않는 경우
    back(current + 1, ssum + arr[current]); // arr[current]를 더하는 경우
}

int main() {
    cin >> n >> s;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    back(0, 0);

    // 크기가 양수인 부분수열만 카운트 해야 하는데, s==0인 경우는 공집합도 포함될 수 있어 -1 필요
    if (s == 0)
        cout << cnt - 1;
    else
        cout << cnt;
}