[Algorithm] 합이 같은 부분 집합(DFS:아마존 인터뷰)

설명

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때

두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고,

그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.

 

입력

첫 번째 줄에 자연수 N(1<=N<=10)이 주어진다.

두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다.

 

출력

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

 

 

풀이.

public class Main {

    static int n; // 주어진 원소 갯수.
    static int total; // 주어진 원소의 전체 합.
    static int[] arr; // 주어진 원소를 담을 배열.
    static boolean flag = false; // 찾기전 flag값 false
    static String result = "NO"; // 출력 결과값 NO로 초기화.

    static void DFS(int level , int sum) {
        if(flag) return; // false 일때만 진행되도록. 한번만 정답이 나오면 YES니깐.
        if(sum > total/2) return; // total/2가 현재까지 구한 sum보다 크면 그 아래로 구할 필요 없다.
        if(level == n){
            if((total-sum) == sum){ // 나누기2 로 사용할 경우 반올림으로 예외 상황 발생할 수 있음.
                result = "YES";
                flag = true; // 한번 YES가 나오면 flag = true 그후로 타는 재귀함수는 전부 return된다.
            }
        }else{
            // 현재의 다음 레벨과 배열의 현재레벨 인덱스 값을 sum에 누적 후 전달.
            DFS(level+1,sum+arr[level]);
            // 현재의 다음 레벨과 기존에 누적된 sum을 전달
            DFS(level+1,sum);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt(); // 배열에 n개의 원소를 대입.
            total += arr[i]; // 배열값을 total에 누적.
        }
        // 레벨과 sum의 인덱스는 1차이 -> 레벨은 1 2 3 4 5 6 / sum의 인덱스는 0 1 2 3 4 5
        DFS(0, 0);
        System.out.println(result);
    }
}

---

정리 :

처음 트리로 구상 할 때 약 원소가 3개일 경우 포함시킬지(O), 포함시키지 않을지(X) 경우의 수(간선의 수)가 3x2=6이다.