[알고리즘/인프런] 합이 같은 부분집합

문제 

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

예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이
16으로 같은 경우가 존재하는 것을 알 수 있다.

 

풀이

다음에 유의하여 풀었다.

1. reduce를 사용할 때는 항상 안전하게 초기값을 정해주자.
2. 부분 집합을 구할 시, 모든 원소를 포함할 것인지, 포함하지 않을 것인지를 확인하면서 끝까지(L===n) 갔을 때 하나의 부분 집합이 완성된다는 것을 기억하자.
3. 이미 답이 결정나서 재귀함수 안에서 종료하고 싶다면 flag를 지정해준다. 프로그램을 종료시키는 exit와 같은 함수는 좋지 않다. 지정해준 flag가 true(1)인 경우에 바로 return한다. 재귀함수 안에서 그냥 return을 하면 해당 함수만 종료되지 남은 것들은 모두 다시 실행되므로 flag를 사용하는 것이다. 주의하자 !
4. 각 재귀함수를 지날 때마다 개수를 세거나 합을 구해야하는 경우 매개변수로 같이 넘겨주면 된다.

 

 

#1

function solution(arr) {
  const n = arr.length;
  const totalSum = arr.reduce((acc, val) => acc + val, 0);
  let answer = "NO";
  let flag = 0;

  function DFS(L, sum) {
    if (flag) return;
    if (L === n) {
      if (sum === totalSum - sum) answer = "YES";
      flag = 1; 
    } else {
      DFS(L + 1, sum + arr[L]);
      DFS(L + 1, sum);
    }
  }

  DFS(0, 0);
  return answer;
}

 

#2

function solution(arr) {
  const total = arr.reduce((acc, cur) => acc + cur);
  const n = arr.length;
  let answer = "NO";
  let ch = Array.from({ length: arr.length }, () => 0);

  function DFS(L) {
    if (L === n) {
      const sum = ch.reduce((acc, cur, idx) => {
        if (cur === 1) acc += arr[idx];
        return acc;
      }, 0);

      if (sum === total - sum) {
        answer = "YES";
      }
    } else {
      ch[L] = 1;
      DFS(L + 1);
      ch[L] = 0;
      DFS(L + 1);
    }
  }
  DFS(0);
  return answer;
}