[Algorithm] 합이 같은 부분집합 (DFS) - JAVA

📌 문제

 

💡 해결

import java.util.*;
public class Exercise01 {
    static String answer = "NO";
    static int n, total = 0;
    boolean flag = false;
    
    // 1) 첫 번째 원소부터 경우의 수를 체크한다.
    // 2) 해당 원소가 더해진 경우(20번째줄) 와 더해지지 않는 경우(21번째줄) 나누어서 체크한다.
    // 3) 구해진 부분집합의 합들 중에서 total 합의 절반의 값이 있다면 
    //    두 부분집합이 같은 경우 이므로 YES를 return한다.
    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){
        Exercise01 ex = new Exercise01();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
            total+= arr[i];
        }
        ex.DFS(0, 0, arr);
        System.out.println(answer);
    }
}

- 해당 문제 풀이를 듣고 이해가 가지 않아서 노트에 하나하나 코드를 그려가며 이해했다. 

- DFS, BFS 이해가도록 더 공부해야한다.