49. 합이 같은 부분집합(DFS)

 

 

 

▣ 입력예제 

 

 

6

1 3 5 6 7 10

 

 

▣ 출력예제 

 

 

YES

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, total = 0, a[11], 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()
{
	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}

	DFS(1,0);

	if (flag == true)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}