합이 같은 부분집합 (DFS)

 

1. DFS 사용하여 부분 집합을 구한다.

{1, 3, 5, 6, 7, 10}

2. 이진 트리 형태 요소의 포함여부로 (O,X) 결정.

//for (int i = 0 ; i < n ; i++) { ch[i]=1; DFS() ch[i]=0;} //처음 실수 했던 n X n 형태.. 답은 나오지만 불필요한 중복 계산이 너무 많다.

//위의 경우 level을 통해 원소의 개수를 파악할 수 있다. 

 

class Main {

	static int n,m;		
	boolean flag = false;
	static String answer="NO";

	public void DFS ( int level, int sum, int [] arr) {
		
		if ( flag ) return;
		
		if (n == level) {
			if( sum*2 == m ) {
				answer = "YES";
				flag = true;
			}
		} else {			
			//이진 트리형태, 현재값을 더한 경우, 안한 경우
			DFS(level + 1, sum + arr[level] , arr);
			DFS(level + 1, sum, arr);	
			
			//for (int i = 0 ; i < n ; i++) { ch[i]=1; DFS() ch[i]=0;} //처음 실수 했던 형태.. 위의 경우 level을 통해 원소의 개수를 파악할 수 있다. 
		}
		
		
	}
	
	
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);		
		
		n = in.nextInt();
		
		int [] arr = new int[n];
		for ( int i = 0 ; i < n ; ++i) {
			arr[i] = in.nextInt();	
		}
		m  = Arrays.stream(arr).sum();
				
		M.DFS(0, 0, arr);
		System.out.println(answer);
		
	}
}

ex)
input
6
1 3 5 6 7 10
output
YES