Inflearn Community Q&A

안녕하세요 강사님.

합이 같은 부분집합 문제에서, 강사님께선 종료조건을
(total - sum) == sum 이걸로 주셨는데,

앞쪽에서 (total / 2) == sum 이것두 된다고하셔서 바꿔서 내봤는데 오답으로 뜨네요,,,

import java.io.*;
import java.util.StringTokenizer;

public class Main {

  static int[] array;
  static int n;
  static int total = 0;
  static boolean isFind = false;
  static String answer = "NO";

  public void DFS(int i, int sum) {
    if (isFind) {
      return;
    }
    if (sum > (total / 2)) {
      return;
    }
    if (i == n) {
      if ((total / 2) == sum) {
        isFind = true;
        answer = "YES";
      }
    } else {
      DFS(i + 1, sum + array[i]);
      DFS(i + 1, sum);
    }
  }

  public static void main(String[] args) throws IOException {
    Main main = new Main();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    array = new int[n];
    String s = br.readLine();
    StringTokenizer st = new StringTokenizer(s, " ");
    for (int i = 0; i < n; i++) {
      array[i] = Integer.parseInt(st.nextToken());
      total += array[i];
    }
    main.DFS(0, 0);
    System.out.println(answer);