[Algorithm] C++ 합이 같은 부분집합(DFS)

입력예제 1

6 

1 3 5 6 7 10

 

출력예제 1

YES

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
int n, a[11], total = 10;
bool flag = false;
void DFS(int L, int sum) {
	if (sum > (total / 2)) return;
	if (flag == true) return;
	if (L == n + 1) {
		if (sum == (total - sum)) {
			flag = true;
		}
	}
	else {
		DFS(L + 1, sum + a[L]); // 누적되는과정
		DFS(L + 1, sum); // 사용하지 않을것이면 그냥 가는 것
	}
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		total += a[i];
	}
	DFS(1, 0);
	if (flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}