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

분류: 백트래킹, 조합 /

 

문제

문제 링크

문제 설명

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

풀이

#include <iostream>
using namespace std;

int N, S, ans;
int num[40];

void backTracking(int cur, int acc) {
    if(cur == N) {
        if(acc == S) ans++;
        return;
    }
    backTracking(cur+1, acc);
    backTracking(cur+1, acc + num[cur]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> S;
    for(int i=0; i<N; i++) cin >> num[i];
    backTracking(0, 0);
    if(S == 0) ans--;
    cout << ans;
}

현재값(`arr[cur]`)을 더할지 안 더할지 판단하며 이진트리 형태의 상태공간 트리를 내려간다.

전체 트리의 리프노드는 전체 부분집합의 수인 2ⁿ개이다.

안 더한 가지가 왼쪽, 더한 가지가 오른쪽이라 하면 가장 왼쪽에는 공집합이, 가장 오른쪽에는 전체집합이 위치한다.

문제에서 크기가 양수인 부분집합만 다루기 때문에 `S = 0`일때 공집합이 답에 포함되는 경우를 제외해줘야한다.(`if(S == 0) ans--;`)