[백준 알고리즘][백트래킹] 1182번 부분집합의 합

문제

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

입력과 출력

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

출력은 합이 S가 되는 부분집합의 개수이다.

문제 출처: 백준 온라인 저지 https://www.acmicpc.net/problem/1182

풀이

제목 그대로 숫자들의 집합이 들어오고, 그 집합들의 합을 통해서 입력한 합을 만들어낼 수 있는지를 알아내야한다. 가능한지를 알아내는 문제가 아니라 합이 S가 되는 부분집합의 개수를 알아내야하므로 모든 부분집합을 다 알아봐야한다. 하나의 원소에 대해서 이 원소를 더하는 경우, 더하지 않는 경우로 트리를 만들어서 뻗어나가게 해야한다. 순간 만약에 탐색을 하다가 더해진 합이 주어진 합보다 크면 탐색을 그만해야한다고 생각을 했는데, 음수도 입력으로 들어올 수 있기때문에 이 문제의 경우는 완전히 모든 경우를 다 탐색해야한다.

생각나는대로 코드를 짰는데 문제가 생겼다. 처음 sum = 0 으로 초기화를 했는데 만약 더해서 나와야하는 합 S가 0으로 들어오면 아무 원소를 포함하지 않을 경우에 cnt가 +1 되어버린다. 현재 합을 만든 원소의 개수가 몇개인지를 나타내주는 변수가 필요할 것 같다.

위에 떠오른 생각때문에 include라는 변수를 만들었는데 또 문제가 생겼다. sum에 더하는데 너무 복잡해진다 ㅠㅠ 그래서 무조건 sum 이 S와 같은지를 볼때 sum+num[current]로 고쳐서 sum 이 하나도 안더해진 0에서 시작하는 일이 없도록 고쳤다. include 변수를 무조건 써서 해볼려고 했는데 실패했다...

코드

#include<stdio.h>

int num[21];

int sum=0; //탐색할 때의 원소들의 합

int cnt; //합이 S가 되는 부분집합의 수

int n, S;

int include = 0;

void BFS(int current);

int main()

{

int i;

scanf("%d %d", &n, &S);

for(i=0 ; i<n ; i++)

scanf("%d", &num[i]);

BFS(0);

printf("%d\n", cnt);

return 0;

}

void BFS(int current)

{

if(current == n) return ;

if(sum + num[current] == S) cnt++;

// 합이 S가 될 경우 부분집합 수 ++해주기

if(current == n) return ;

BFS(current+1);  //현재 원소를 안 더하고 탐색하는 경우

sum += num[current]; //현재 원소를 더하고 탐색할 경우

BFS(current+1);

sum -= num[current]; //다음 경우를 위해 다시 원래 sum으로 만들어줌

}