[ 자바스크립트(JavaScript) ] section08 - 5 - 합이 같은 부분집합(DFS: 아마존 인터뷰)

📍 section08 - 5 - 합이 같은 부분집합(DFS: 아마존 인터뷰)

N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나눌 때 두 부분집합의 원소의 합이 서로 같은 경우면 YES, 그렇지 않으면 NO를 출력하는 프로그램을 작성하는 문제다. 마찬가지로 순서도를 그려서 이해하는 것이 가장 빠르나, 입력 예제가 n=6이므로(총 64개의 가지를 그려야함) 따로 순서도를 그리지 않고 그림처럼 그리면 된다.

 

1. 어떤 부분집합의 합이 같은지를 찾으려면 부분집합이 나올 수 있는 경우의 수를 모두 구한다. n=6이므로 총 부분집합의 개수는 2^6=64가 나온다.
2. 합이 같은 부분집합을 찾을 때, A, B 부분집합을 모두 구하지 않고 한 부분집합만 구하고 나서 sum(배열) - aSum(한 부분집합) = aSum이면 aSum = bSum이 된다.
3. 11번째 코드에 edgeCut 방식을 적용했는데, edgeCut이란 문제에서 주어진 출력을 만족하여 더 이상 계산 할 필요 없을 때 남은 재귀를 거치지 않고 return하여 출력하는 방식이다. 불 필요한 계산을 줄여 시간을 조금이나마 더 단축할 수 있는 장점이 있다.

 

728x90

 

let n = 6;
let arr = [1, 3, 5, 6, 7, 10];

console.log(solution(n, arr));

function solution(n, arr){
  let total = arr.reduce((prev, cur) => prev+cur);
  let flag = false;

  function DFS(L, sum){
    if (flag) return;  // edge cut
    if (L === n){
      if (total-sum===sum) flag = true
    }else{
      DFS(L+1, sum+arr[L]);
      DFS(L+1, sum);
    }
  }

  DFS(0, 0);
  return flag ? "YES" : "NO";
}