[알골90제] 60번 - 합이 같은 부분집합 : DFS (아마존인터뷰)

* 문제

 

N개의 원소로 구성된 자연수 집합이 주어짐

이 집합을 두개의 부분집합으로 나눔

ex. 1 3 5 6 7 10 을 1 3 5 7 과 6, 10 으로 그리고 두 부분집합의 합이 같은 경우가 존재하는지 확인

부분집합의 합이 같은 경우가 있다면 YES 출력 아니면 NO 출력

 

단, 입력에서 원소는 중복되지 않는다.

 

* 풀이 

 

- 재귀함수를 돌리면서 부분집합을 구함

- 남아있는 원소들 즉, 사용하지 않은 부분집합도 만들어짐

 

- total에다가 입력받은 원소를 다 더함

- 재귀로 부분집합을 만들어서 합을 만듬 sum

- 남아 있는 원소들의 합은 total - sum 이 같으면 두 부분집합이 같은 것임

- 두 부분집합의 합은 같아야 하기 때문에 한쪽의 부분집합의 합이 절반이상이면 항상 NO됨 (다른 한쪽이 작아지니깐 같을 수 없기때문)

 

//60번 - 합이 같은 부분집합 DFS 아마존 인터뷰

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
int n, a[11], total=0;
bool flag = false;

void DFS(int L, int sum) { //sum으로 부분집합 합 컨트롤 할것임
	
	if (sum > total / 2) return; //2개의 부분집합 합이 같아야하니 절반이상은 될 수 X
	if (flag == true) return;

	if (L == n+1) {
		if (sum == (total - sum)) {
			flag = true;
		}
	}
	else {
		DFS(L + 1, sum + a[L]); //level증가 sum은 누적
		DFS(L + 1, sum); //level증가 sum은 사용X
	}
}


int main() {

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		total += a[i];
	}

	DFS(1, 0); //level과 원소의 합이 넘어감
	if (flag == true) printf("YES");
	else printf("NO");

	return 0;
}