합이 같은 부분집합(아마존 인터뷰, DFS:완전탐색) / c / 제한시간 없음

▣ 문제

- N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

▣ 출력설명

- 첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

 

▣ 입력설명

6 1 3 5 6 7 10

 

▣ 입력설명

YES

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int n, i;
int num[11];
int check[11] = { 0 };
int flag = 0;
int a = 0, b = 0;

void dfs(int x) {
	if (x == n + 1) {
		for (i = 1; i <= n; i++) {
			if (check[i] == 0) a += num[i];
			else b += num[i];
		}
		if (a == b) flag = 1;
		a = 0;
		b = 0;
		return;
	}
	check[x] = 1;
	dfs(x + 1);
	check[x] = 0;
	dfs(x + 1);
}

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

이전 부분집합 문제와 동일하게 풀었다.

 

n+1 레벨에서 check가 1인 숫자와 0인 숫자들을 각각 더해서 두 합이 같을때 flag를 1로 만들어주었다.

 

dfs 함수가 끝나고 flag가 1이면 'YES' 0이면 'NO'를 출력했다.

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdbool.h>
int n, i;
int total = 0;
int num[11];
bool flag = false;

void dfs(int L, int sum) {
	if (L == n + 1) {
		if (flag == true) return;
		if (L == n + 1) {
			if (sum == (total - sum)) flag = true;
		}
	}
	else {
		dfs(L + 1, sum + num[L]);
		dfs(L + 1, sum);
	}
}

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

	return 0;
}

처음 main 함수에서 집합을 입력받을때 total이라는 변수에 모든 원소의 합을 구한다.

 

dfs 함수에서 오른쪽 자식은 num[L]을 포함하고 왼쪽 자식은 포함하지 않는다.

 

이떄 dfs에 레벨값말고 sum도 같이 사용한다. dfs(L + 1, sum + num[L]) 를 통해서 오른쪽 노드로 갈때 체크하는 부분집합을 sum에 계속 더해준다.

 

n+1레벨까지 갔을때 sum의 값이 total의 절반이 된다면 부분집합의 합이 같다는 뜻이기 때문에 flag를 true로 바꿔준다.

 

그리고 flag가 한번이라도 true가 된다면 나머지는 굳이 계산을 할 필요가 없기 때문에 if (flag == true) return; 를 계산하는 코드 앞에 사용한다.

 

.

 

문제를 풀때 직접 노드를 그리고 계산하는 과정을 익숙하게 해야 dfs문제를 쉽게 풀수있다.