[알고리즘] 8-1 합이 같은 부분집합 - DFS(깊이우선탐색) , 아마존 인터뷰 (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/08-01
• 문제 설명 : n개의 원소를 가진 자연수 집합이 주어지고, 이 집합을 두 개의 부분집합으로 나눴을 때 각 부분집합의 원소의 합이 서로 같은 경우가 존재하는지 묻는 문제

풀이

• DFS(깊이우선탐색)을 진행하며 부분집합 경우의 수를 구한다.
• 한 부분집합의 합이 전체 집합의 합의 절반이면 두 부분집합의 합이 같다
• 참고 : 부분집합 구하기 문제 - DFS

package inflearn.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//합이 같은 부분집합(DFS : 아마존 인터뷰)
public class Main8_1 {

    //전체 집합 원소의 총합
    static int total = 0;

    static int n;
    static String answer = "NO";

    //두 부분 집합의 합이 같을 떄, 나머지 메서드들을 실행하지 않도록하는 용도
    static boolean flag = false;

    /**
     * @param idx : 대상 원소의 배열 인덱스
     * @param sum : 현재까지 부분 원소의 합
     */
    public static void dfs(int idx, int sum, int[] arr) {
        if (flag)
            return;

        //부분집합의 합이 total 값의 절반을 넘어서면 이미 정답이 될 수 없다.
        if (sum > (total/2))
            return;

        if (idx == n) {
            //total값이 홀수 일때도 나머지연산은 몫을 구하기 때문에
            //(예를 들어 total 값이 125일 경우 sum이 62이면 참이 되버린다.)
            //그래서 나머지가 0인 조건을 추가한다.
            //(또는 뺼셈을 사용하자. (total-sum) = sum)
            if (total%2 == 0 && total/2 == sum) {
                answer = "YES";
                flag = true;
            }
        } else {
            //해당 원소를 포함하는 경우
            dfs(idx + 1, sum + arr[idx], arr); 

            //해당 원소를 포함하지 않는 경우
            dfs(idx + 1, sum, arr); 
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            total += arr[i];
        }

        dfs(0, 0, arr);

        System.out.println(answer);
    }
}