IF - 합이 같은 부분집합

문제

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면
”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의
집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이
16으로 같은 경우가 존재하는 것을 알 수 있다.

예시

Input	Output
[1,3,5,6,7,10]	YES

풀이 및 회고

• 주어진 배열에서 각 원소가 계산에 포함될 경우와 포함되지 않을 경우를 이진트리로 나눠 DFS 알고리즘으로 탐색한다.
• DFS 가 트리의 맨 끝까지 탐색했을 때 계산을 시작한다.
• 미리 만들어둔 체크배열을 돌면서 문제에서 주어진 배열과 같은 인덱스의 체크배열의 원소 값이 1 이면 sum 변수에 합한다.
• sum 이 문제에서 주어진 배열의 총 합의 1/2 면, 집합에 포함된 숫자들의 합과 포함되지 않은 숫자들의 합이 같다는 것을 알 수 있다. 따라서 두 집합은 서로소 집합이다.
• 이제 좀 DFS 알고리즘의 로직이 감이 오는 것 같다.

코드

const solution = (nums) => {
  let answer = "NO";
  let flag = 0;
  const check = new Array(nums.length);
  check.fill(1);
  const total = nums.reduce((acc, cur) => acc + cur, 0);

  const DFS = (dt) => {
    if (flag) return;
    if (dt === nums.length + 1) {
      let sum = 0;
      for (let i = 0; i < check.length; i++) {
        if (check[i] === 1) {
          sum += nums[i];
        }
      }

      if (sum * 2 === total) {
        answer = "YES";
        flag = 1;
      }
    } else {
      check[dt] = 1;
      DFS(dt + 1);
      check[dt] = 0;
      DFS(dt + 1);
    }
  };

  DFS(1);
  return answer;
};