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

 

설명

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

 

 

 

 

입출력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

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

 

 

 

예시

6

1 3 5 6 7 10

 

YES

 

 

 

 

풀이

1. 부분집합을 한개씩 출력하는게 아니므로 굳이 check배열 쓸 필요는 없다.

하지만 sum변수를 써서 DFS를 하나씩 수행할때마다 합을 누적해주어야한다.

 

2. 만약 sum==total의 절반과 같아진다면 그 경우에 정답은 "YES"가 된다.

import java.util.*;
class Main {
	static int n;
	static int[] arr;
	static String answer="NO";
	static int total =0;
	static boolean flag=false;
	
	public void DFS(int L, int sum) {
		if(flag) {
			return;
		}
		if(sum>(total/2)) {
			return;
		}
		if(L==n) {
			if((total-sum)==sum) {
				answer="YES";
				flag=true;
				return;
			}
		}else {
			DFS(L+1, sum+arr[L]);
			DFS(L+1, sum);
		}
	}
	
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		arr= new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
			total+=arr[i];
		}
		T.DFS(0,0);
		System.out.println(answer);
	}	
}