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

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

1182번: 부분수열의 합

#include <iostream>
using namespace std;

int n,s;
int arr[30];
int cnt;

void func(int cur, int tot){
    if(cur == n) 
    { 
        if(tot == s){
        	cnt++;
		} 
        return ;
    }
    func(cur+1, tot);
    func(cur+1, tot + arr[cur]);
}
int main(void)
{
    cin >> n >> s;           // 5 0
    for(int i=0; i<n; i++)
        cin >> arr[i];       // -7 -3 -2 5 8
    func(0, 0);
    if(s==0) cnt--;
    cout << cnt;
}

 

- 백트래킹문제. 재귀로 모든 경우의수를 어떻게 살필 수 있을까를 고민해야할 문제

 

예시 입력 )

5 0

-7 -3 -2 5 8

일 때를 살펴보면 나올 수 있는 모든 집합은 

[[], [-7], [-7, -3], [-7, -3, 5], [-7, -3, 5, -2], [-7, -3, 5, -2, 8], [- 7, -3, 5, 8], [-7, -3, -2], [-7, -3, -2, 8], [-7, -3, 8], [-7, 5], [-7, 5, -2], [-7, 5, -2, 8], [-7, 5, 8], [-7, -2], [-7, -2, 8], [-7, 8], [-3], [-3, 5], [-3, 5, -2], [-3, 5, -2, 8], [-3, 5, 8], [-3, -2], [-3, -2, 8], [-3, 8], [5], [5, -2], [5, -2, 8], [5, 8], [-2], [-2, 8], [8]]

나올 수 있는 모든 합의 경우는

[0, 1, 2, 3, 4, 5, 6, 8, 10, 11, 13, -12, -10, -9, -2, -7, -5, -4, -3, -1]

 

모든 경우를 트리로 표현

- 간단하게 만든 트리 그림을 보면 이해가 좀 쉽다.

입력으로 받은 n은 5이니, 노드의 깊이는 5가 된다.

노드가 하나씩 증가하면 추가 여부를 살필 배열의 인덱스도 하나씩 늘어난다. (하단에 숫자를 따라가면서 보면 쉬움)

 

- 여기서 헷갈리면 안되는 부분은!

노드를 확장해나가면서 조건에 부합되면 빠져나오는게 아니라,

노드를 끝까지 확장했을때 조건에 부합되는지 판단해야하는 것이다.

 

- 함수의 매개변수 역할을 살펴볼때

func(노드의 깊이 판단, 부분 합 건네주기) 정도로 보면 될 것 같다.