[Algorithm] 합이 같은 부분집합(이진트리 DFS)

이진 트리에 익숙해지기 위한 반복 문제이다. 서로소인 부분 합 2개의 합이 같은 지 확인하라고 한다.

const input = require("fs").readFileSync("example.txt").toString().split("\n");
const n = Number(input[0]);
const arr = input[1].split(" ").map(Number);
arr.unshift(0);
const sum = arr.reduce((a, b) => a + b, 0);
let check = new Array(n + 1).fill(0);
let answer = "NO";
const DFS = (num) => {
  if (num == n + 1) {
    let matched = [];
    for (let i = 1; i <= n; i++) {
      if (check[i] == 1) {
        matched.push(arr[i]);
      }
    }
    if (sum == matched.reduce((a, b) => a + b, 0) * 2) {
      answer = "YES";
      return;
    }

    return;
  } else {
    check[num] = 1;
    DFS(num + 1);
    check[num] = 0;
    DFS(num + 1);
  }
};

DFS(1);
console.log(answer);

이 전과 똑같고 합만 구해주면 된다. 추가적으로 전체합이 부분합의 2배인지 체크해주면 됨.