60. 합이 같은 부분 집합 (아마존 인터뷰 문제 : DFS 완전탐색) [재귀 & 깊이/넓이 우선탐색(DFS, BFS)]

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;
int arr[11];
int arrSum[1025];
int cnt = 0;
bool yes = false;

void DFS(int maxLevel, int curLevel, int* a) {
	if (yes == true) return;
	int* ar = new int[maxLevel];
	int sum = 0;
	int remainSum = 0;
	for (int i = 0; i < maxLevel; i++) {
		ar[i] = a[i];
	}
	
	if (curLevel > maxLevel) {
		for (int i = 0; i < maxLevel; i++) {
			if (ar[i] == 1) sum += arr[i];
		}
		for (int i = 0; i < maxLevel; i++) {
			if (ar[i] == 0) remainSum += arr[i];
		}
		if (sum == remainSum) yes = true;
		return;		
	}
	else {
		a[curLevel - 1] = 1;
		DFS(maxLevel, curLevel + 1, a);
		a[curLevel - 1] = 0;
		DFS(maxLevel, curLevel + 1, a);
	}	
}

int TwoSquare(int num) {
	int res = 1;
	for (int i = 0; i < num; i++) {
		res *= 2;
	}
	return res;
}


int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n;
	scanf("%d", &n);
	int square = TwoSquare(n);

	int* a = new int[n];
	for (int i = 0; i < n; i++)
		a[i] = 1;

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
		
	DFS(n, 1, a);	

	if (yes) printf("YES");
	else printf("NO");
	
	delete[] a;
}