8. 합이 같은 부분집합(DFS 완전탐색 : 아마존 인터뷰)

 

    8번 문제   

 

 

---

 

 

    내가 풀이한 답   

 앞의 7번 문제를 응용하면 쉽게 풀 수 있다. 

 

 

 

 두 개의 부분집합으로 나뉘기 때문에 부분집합의 총 합과 (전체 총 합 - 부분집합의 총 합)이 같으면 두 부분 집합이 같게 된 점을 이용하면 쉽게 풀 수 있다.

 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, a[11], total=0;
bool flag = false;

void dfs(int level, int sum){
	if(level == n+1){
		if(total-sum == sum) flag = true; 
	}
	else {
		dfs(level+1, sum+a[level]);
		dfs(level+1, sum);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i;
	cin >> n;
	for(i=1; i<=n; i++){
		cin >> a[i];
		total+=a[i];
	}
	
	dfs(1, 0);
	
	if(flag) cout << "YES";
	else cout << "NO";
	
	return 0;
}

 

---

    사이트의 답안   

#include<stdio.h>
int n, a[11], total=0;
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(){
	freopen("input.txt", "rt", stdin);
	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;
}