DFS)합이 같은 부분집합

문제

 

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하라. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 

 

▣ 입력설명 첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며 그 크기는 1,000,000 이하이다.

 

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

 

▣ 입력예제 1

6

1 3 5 6 7 10

▣ 출력예제 1

YES

 

 

코드

int sum1 = 0, sum2 = 0;
vector<int>arr1;
int total = 0;
bool ch = false;
void DFS(int num)
{
	if (total-sum1-sum2==0&&sum1 == sum2)
	{
		ch = true;
		return;
	}
	else
	{
		if (num < arr1.size())
		{

			sum1 += arr1[num];
			DFS(num + 1);
			sum1 -= arr1[num];

			sum2 += arr1[num];
			DFS(num + 1);
			sum2 -= arr1[num];
		}
	}

}

int level;

int main()
{
	int MAX = 10000000;
	int a, b;
	int node, dest, cost;
	int res = 0;
	cin >> level;

	for (int i = 0; i < level; i++)
	{
		cin >> a;
		total += a;
		arr1.push_back(a);

	}

	DFS(0);

	if (ch == true)cout << "YES";
	else cout << "NO";



}