Q. (X)

---

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

실패 요인

ch배열을 만들 필요가 없다. sum으로 누적하는것 자체가 부분집합에 포함시키는 행위임

전략

정답

import java.util.*;
class Main{
    // main()에서도 써야해서 static
    static String answer="NO";
    static int n, total=0;
    boolean flag=false;
    public void DFS(int L, int sum, int[] arr){
        if(flag) return;
        // sum>total/2인 경우에만, 해당 부분집합을 완성시킬 필요 없으므로 다른 경로로 재귀하도록 리턴
        if(sum>total/2) return;
        // 부분집합 완성
        // L이 0번 인덱스부터이므로 L==n+1이 아니라 L==n
        if(L==n){
            // sum이 total의 절반일 때
            if((total-sum)==sum){
                answer="YES";
                // 앞으로의 재귀를 모두 멈춘다 
                // (이미 쌓여있던 스택으로 복귀해서 호출한 재귀를 바로 리턴) 
                // 복귀해서 호출한 재귀 분 외에는 새롭게 뻗지 않음
                flag=true;
            }
        }
        else{
            // sum+arr[L] : +arr[L]를 부분집합에 포함시킴
            DFS(L+1, sum+arr[L], arr);
            // sum : arr[L]를 부분집합에 포함시키지 않음
            DFS(L+1, sum, arr);
        }
    }
    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        int[] arr=new int[n];
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
            total+=arr[i];
        }
        // L은 arr의 인덱스 (0부터)
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }
}