#합이 같은 부분집합(DFS)

 

 

부분집합 구하기 문제처럼 해당 숫자를 사용한다/사용하지 않는다로 재귀호출 했던 것 처럼

여기선 해당 인덱스의 원소를 부분집합의 합으로 사용한다/사용하지 않는다라고 재귀호출

L번째 인덱스에 있는 숫자를 더한다/더하지않는다 인것!

L == n 이 되면 모두 더하는 것 ~ 모두 더하지 않는 것에 대한 조합(?)들이 만들어진다.

매개변수로는 사용여부에 따라 합칠 숫자의 갯수, 합칠 숫자들의 합, 배열로 설정한다.

 

import java.util.*;

public class Main {
    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이 절반보다 높으면 굳이 더 내려갈 필요없음
        if(sum>total/2) return;
        //부분 집합이 완성되면
        if(L==n){
            //sum이 total의 절반인 것.
            if((total-sum) == sum) {
                answer = "YES";
                flag=true;
            }
        } else {
            //부분 집합에 현재 숫자를 포함한다.
            DFS(L+1, sum+arr[L], arr);
            //부분 집합에 현재 숫자를 포함하지 않는다.
            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];
        }
        T.DFS(0, 0, arr);
        System.out.println(answer);
    }

}