60.합이 같은 부분집합

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

#include

using namespace std;

int n,i,a[11],total=0,sum=0;
bool flag=false;
void DFS(int L,int sum){
if((total/2)<sum){ //sum이 절반보다 높으면 더 이상 볼필요x
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(i=1;i<=n;i++){
	cin>>a[i];
	total+=a[i];
}

DFS(1, 0); // level 과 합 

if(flag) cout<<"YES";
else cout<<"NO";

return 0;

}