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

문제

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

풀이

 

function solution(arr) {
  let answer = "NO",
    flag = 0;
  let total = arr.reduce((sum, item) => sum + item, 0);
  function DFS(L, sum) {
    if (flag) return;
    if (L === arr.length) {
      if (total - sum === sum) {
        answer = "YES";
        flag = 1;
      }
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }
  DFS(0, 0);
  return answer;
}

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

 

flag를 통해 답이 찾아진다면 그 외의 재귀 함수를 진행할 필요가 없으니 바로 종료하는 법을 배우게 되었고 DFS 함수에 매개변수 2개를 이용해보았습니다