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

🥫 문제

🥫 풀이

부분집합의 합 구하는 아이디어

가지치기를 하자.
DFS 메소드를 이용해 DFS()의 첫번째 인자는 몇번째 인지, 2번째 인자는 합을, 3번째 인자는 배열을 넣어준다.

DFS 메소드

 public void DFS(int L, int sum, int[] arr){
        if(flag) return;

        if(sum > total/2)
            return;

        if(L == n){
            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) {
        Main65 T = new Main65();
        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);
    }

🥫 소스코드

package algolecture;

import java.util.Scanner;

public class Main65 {
    static String answer = "NO";
    static int n,total = 0;
    boolean flag = false;

    public void DFS(int L, int sum, int[] arr){
        if(flag) return;

        if(sum > total/2)
            return;

        if(L == n){
            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) {
        Main65 T = new Main65();
        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);
    }
}