[인프런] 08_01 합이 같은 부분집합(DFS : 아마존 인터뷰)

📖  문제

---

• N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.

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

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

   

  

⚠️  주의사항

---

• 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 돼야 하므로 끝까지 비교 후 합이 같은 부분집합이 있는지 확인
• 서로소 집합

✍️  이해

---

/**
 * 1. N개 배열 입력
 * 2. 원소의 합이 서로 같은 경우 이므로 원소의 합은 배열의 합의 / 2
 * 3. 배열의 모든 값 비교 후 2번의 조건과 동일하면 answer = "YES" 변경 후 return
 */

 

 

✏️  풀이

---

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int[] arr;
    static String answer;
    static int total , N;

    public void DFS(int L, int sum, int[] arr) {
        if (sum > total / 2) return;

        if (L == N) {
            if ((total / 2) == sum) {
                answer = "YES";
                return;
            }
        }else{
            DFS(L + 1, sum + arr[L], arr);
            DFS(L + 1, sum, arr);
        }
    }

    public static void main(String[] args) {

        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        answer = "NO";
        N = sc.nextInt();
        arr = new int[N];

        for (int i = 0; i < N; i++) arr[i] = sc.nextInt();
        total = Arrays.stream(arr).sum();

        T.DFS(0, 0, arr);

        System.out.println(answer);
    }
}

---