60. 합이 같은 부분집합(DFS : 아마존 인터뷰) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

#include <stdio.h>
#include <cmath>

int n;
int a[11];
int b[100];
int c[1025];
int sum;
int idx = 1;

void DFS(int x)
{
	if(x == n+1)
	{
		sum = 0;
		for(int i = 1; i <= n; i++)
			if(b[a[i]] == 1)
				sum += a[i];
		c[idx++] = sum;
	}
	else
	{
		b[a[x]] = 1;
		DFS(x+1);
		b[a[x]] = 0;
		DFS(x+1);
	}
}

int main()
{
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	DFS(1);
	
	for(int i = 1; i <= pow(2, n); i++)
	{
		int temp = c[i];
		if(temp == 0)
			continue;
		for(int j = 1; j <= pow(2, n); j++)
		{
			if(i == j)
				continue;
			
			if(temp == c[j])
			{
				printf("YES");
				return 0;
			}
		}
	}
	
	printf("NO");
	return 0;
}

1. 배열 a는 입력된 n개의 정수를 저장, 배열 b는 배열 a의 원소를 idx로 하여 1과 0으로 그 숫자를 포함하는 부분집합인지 아닌지를 나눈다. 배열 c는 각 노드가 가지는 배열 b 의 모든 원소의 합을 갖는다.

2. 배열 c의 전체 원소를 확인해서 서로 같은 값을 가지는 원소가 있다면 YES를 출력하고 그렇지 않다면 NO를 출력한다.

 

강의를 보고 짠 코드

#include <stdio.h>

int n;
int a[11];
int total = 0;

bool flag = false;
void DFS(int x, int sum)
{
	if(sum > (total/2)) return;
	if(flag) return;
	if(x == n+1)
	{
		if(sum == (total/2))
		{
			flag = true;
		}
	}
	else
	{
		DFS(x+1, sum+a[x]);
		DFS(x+1, sum);
	}
}

int main()
{
	scanf("%d", &n);
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		total += a[i];
	}
	
	DFS(1, 0);
	
	if(flag)
		printf("YES");
	else
		printf("NO");
	return 0;
}

1. 이 코드는 DFS() 함수에 매개변수 int sum을 추가했다. 매번 배열 a의 원소를 사용할 것이라면 sum에 더해서 다시 호출하고, 사용하지 않는다면 더하지 않고 다시 호출하는 방식이다.

2. 전체 합을 total 이라고 한다면, 두 부분집합의 합이 total이어야한다. 즉 total/2 와 같아야한다.

3. 한 부분집합의 원소의 합이 전체 합의 반을 넘어간다면, 위 조건에 맞지 않으므로 return

4. 만약 sum == total/2 와 같은 순간이 온다면 더 확인할 필요 없으므로 return

 

4번 문제에 오류가 있는 것 같아 문의함