[JavaScript/section 8] 05 - 합이 같은 부분집합

📌 05 - 합이 같은 부분집합(DFS : 아마존 인터뷰)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력하는 문제이다. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 한다.

👍 풀이 방법

부분집합 구하기 문제의 풀이 과정을 그림으로 그려가면서 이해를 했다면 어렵지 않은 문제이다. 이번 문제 또한 그림을 그리면서 이해를 하였다.

• 배열 요소들의 총 합(total)을 구한다.
• 재귀를 돌다가 탐색하고 있는 idx가 배열의 길이와 같다면 총 합에서 sum(부분 집합의 합)을 뺀 값이 sum과 같은지 비교한다.
• 같은 경우 answer 변수에 'YES', flag(탐색을 멈추기 위한 변수) 변수에 1을 재할당해준다.

 

📝 소스 코드

function solution(arr) {
  let answer = 'NO';
  flag = 0;
  let total = arr.reduce((a, b) => a + b);
  let len = arr.length;

  function DFS(idx, sum) {
    if (flag) return;
    if (idx === len) {
      if (total - sum === sum) {
        answer = 'YES';
        flag = 1;
      }
    } else {
      //   sum += arr[idx];
      DFS(idx + 1, sum + arr[idx]);
      //   sum -= arr[idx];
      DFS(idx + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

let arr = [1, 3, 5, 6, 7, 10];
console.log(solution(arr));