[백트래킹 / BOJ 1182 / C++] 부분수열의 합

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

1182번: 부분수열의 합

 

새로운 주제인 백트래킹이다. 재귀를 응용해서 경우의 수를 찾을 수 있다.

 

문제를 읽어보면 부분집합들의 합을 찾아내야한다. 주어진 1) 수열의 부분집합을 찾고 2)그 부분집합의 합을 구해내는 것이 핵심이다. 그러나 대게 막연할 것이다. 따라서 다음과 같이 그림으로 도식화해보자.

fig.1 간단한 도식화된 그림.(그런데 다이얼그림 그리는거 오래걸리네.... ㅋㅋ큐)

그림을 보며 생각해보자. 위의 그림은 제시된 수열이 {1,2,3}일때를 가정했다.

우선 우리는 최대 3번까지 선택할 수 있다. 수열의 크기가 3이기 때문이다. (참고로 부분집합의 개수는 2^3 = 8 개이다. 공집합이 포함됨!)

 

첫번째로 1을 선택하거나 안할 수 있다.

 - 1을 선택하지 않았다면 현재 수열은 { }

두번째로는 2를 선택하거나 안할 수 있다.

 - 2를 선택하지 않았다면 현재 수열은 { }

마지막으로 3을 선택하거나 안할 수 있다.

 - 3을 선택하지 않았다면 현재 수열은 { }

 

최종적으로 나오는 수열은 { }. (공집합) 따라서 합이 S=5 가 되지 않으므로 해당 부분수열은 세지 않는다.

 

위와 같은 과정을  fig.1 처럼 채워나갈 수 있다. 같은 과정을 반복하니깐 재귀함수를 생각해볼 수 있다.

 

그렇다면 Base Condtion을 생각해보자. 어떻게 하면 함수를 종료시킬 수 있을까 ? 바로 선택의 횟수다. 선택은 무조건 3번해야한다. 모두 선택하지 않거나, {1,2,3}을 선택하거나 무조건 3번. 선택 횟수를 계속해서 넘겨주면 된다. 또한 문제 조건에 맞게 부분합도 계속 구해서 만약 S가 된다면 그 즉시 횟수를 세주면 된다.

 

1) 수열의 크기 만큼 선택을 반복한다.
2) 만약 아무것도 선택하지 않거나 선택했다면, 다음 숫자를 선택하지 말지 결정한다.
3) 선택의 횟수가 N만큼 된다면 함수를 종료 시킨다. 이때, 지금까지 더해준 값이 S가 된다면, cnt를 +1 한다.

 

#include <bits/stdc++.h>
using namespace std;

int N, S, cnt;
int num[21];
bool isused[21];


void func(int n, int sum){ // n=현재 앞에서부터 고른 숫자 개수, sum=현재까지의 합
  if(n==N){
        if(sum==S) cnt++;
        return;
        }
   // base condition

    func(n+1, sum); // 아무것도 추가를 안해줌. (선택 X)
    func(n+1, sum + num[n]) ; // 혹은 추가해줌. (선택 O)
 }


int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> S;
  for(int i = 0 ; i < N ; i ++){
    cin >> num[i];
  }
  func(0, 0);
 if(S==0) cnt--; // S==0일때는 하나를 빼줘야함.

 cout << cnt;
}