Java : 합이 같은 부분집합

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

• 문제점
  • 입력받는 원소 리스트로 dfs 트리를 구현해야하는데 어떻게 짜야할지 감이 안 잡힌다.
  • ‘원소의 합 / 2’ 가 두 부분집합이 가지는 합이다. 이것을 활용할 수 있을까
• 풀이
  • 이진 트리 + DFS 로 풀었다
  • (level = 0 , sum = 0) 으로 root를 두고 lt 는 더할 것 rt 는 더하지 않는 것으로 뿌리를 내린다. root의 (0,1) 은 0레벨, sum = 1(첫 번째 인자 값이 1이므로)로 시작한다는 것이다.
  • 두 집합의 합이 같아야하므로 홀수인 경우는 0.5가 나오므로 그냥 리턴 시켰다.
    • 이 부분에서 예외가 있을 수도 있다.

import java.util.Scanner;
import java.util.Stack;

public class I0802 {

  static int[] ch;
  static int level;
  static int targetSum;

  static boolean flag = false;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ch = new int[n];
    level = 0;
    int totalSum = 0;
    for (int i = 0; i < n; i++) {
      int m = sc.nextInt();
      totalSum += m;
      ch[i] = m;
    }
    targetSum = totalSum / 2;
    if (totalSum % 2 == 1) {
      System.out.println("NO");
    } else {
      dfs((0), ch[0]);
      if (flag) System.out.println("YES");
      else System.out.println("NO");
    }
  }

  static void dfs(int level, int sum) {
    if (level == ch.length - 1) return;
    if (sum == targetSum) {
      flag = true;
      return;
    }
    if (sum > targetSum) return;
    dfs(level + 1, sum + ch[level + 1]);
    dfs(level + 1, sum);
  }
}