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

설명

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

 

문제 해결

 

집합이 주어지면, 이를 두 개로 나눴을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하면 된다. 이 문제도 DFS로 해결할 수 있다.

 

static int N;
static int[] arr;
static int arrSum = 0;
static String result = "NO";

 

먼저 구성될 원소의 개수 N과 원소를 입력받을 배열 arr, 배열들의 모든 합을 저장할 arrSum, 그리고 출력할 String result를 전역변수로 선언해주고 'NO'로 초기화시켜 주었다.

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    arr = new int[N];

    for (int i = 0; i < N; i++) {
        arr[i] = in.nextInt();
        arrSum += arr[i];
    }

    if(arrSum % 2 == 0) {
        DFS(0,0);
    }

    System.out.println(result);
}

 

메인함수에서 arr 배열에 N개의 원소를 다 입력 받은 후 arrSum에 그 원소들을 모두 더해 저장해준다.

그 후 만약 arrSum을 2로 나눴을 때 나머지가 0이 됐을 때 DFS(0,0)을 호출한다. 

만약 0이 되지 않으면 아예 DFS 호출이 필요하지 않기 때문이다.

 

public static void DFS(int L, int currentSum) {
    if (currentSum > arrSum / 2) return;

    if (currentSum == arrSum / 2) {
        result = "YES";
        return;
    }

    if(L==N) return;

    DFS(L+1, currentSum+arr[L]);
    DFS(L+1, currentSum);
}

 

DFS 함수이다. 레벨 L과 현재 원소를 더해가며 져장될 변수인 currentSum을 받는다.

• 그리고 만약 currentSum이 arrSum을 2로 나눈 값보다 크면 return한다.
• 만약 currentSum이 arrSum을 2로 나눈 값과 같다면 2개로 나뉜 부분 집합의 원소의 합이 서로 같은 경우가 존재하는 것이므로 "YES"를 출력하고 return하면 된다.
• L레벨이 N과 같다면 즉 모두 탐색했다면 더 이상 탐색할 것이 없으니 return한다.
• 현재 요소 arr[L]를 부분집합의 합에 포함하는 경우 DFS(L+1, currentSum+arr[L])
  • 현재 요소를 currentSum에 더하고 다음 요소로 넘어감
• 현재 요소 arr[L]를 부분집합의 합에 포함하지 않는 경우 DFS(L+1, currentSum)
  • 현재 요소를 제외하고 다음 요소로 넘어감

 

최종 코드

 

import java.util.Scanner;
public class P01_합이같은부분집합 {

    /** 두 개로 나눴을 때 합이 같은 게 존재하려면, 2/원소들의 합=0이 되는 게 있어야 함 **/
    static int N;
    static int[] arr;
    static int arrSum = 0;
    static String result = "NO";
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
            arrSum += arr[i];
        }

        if(arrSum % 2 == 0) {
            DFS(0,0);
        }

        System.out.println(result);
    }

    public static void DFS(int L, int currentSum) {
        if (currentSum > arrSum / 2) return;

        if (currentSum == arrSum / 2) {
            result = "YES";
            return;
        }

        if(L==N) return;

        DFS(L+1, currentSum+arr[L]);
        DFS(L+1, currentSum);
    }
}