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

부분집합 구하기 문제를 풀고 나서 이 방식으로 문제를 풀었는데, 이 문제의 경우, 각 숫자가 선택이 되었는지의 여부는 크게 중요하지 않고 합만이 중요하므로, sum 매개 변수를 넘겨줘도 크게 메모리 낭비가 없을 것 같다.

내 풀이

function solution(arr) {
  let answer = 'NO';
  let check = Array.from({ length: arr.length }, () => 0);
  let sum = parseInt(arr.reduce((sum, v) => sum + v, 0));
  if (sum % 2 === 1) return 'NO';
  function DFS(k) {
    if (answer === 'YES') return;
    if (k >= check.length - 1) {
      let temp = [];
      for (let i = 0; i < check.length; i++) {
        if (check[i] === 1) temp.push(arr[i]);
      }
      let temp_sum = temp.reduce((sum, v) => sum + v, 0);
      if (temp_sum === parseInt(sum / 2)) answer = 'YES';
      return;
    }
    check[k] = 0;
    DFS(k + 1);
    check[k] = 1;
    DFS(k + 1);
  }
  DFS(0);
  return answer;
}

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

check 배열을 넣었다는 것과 마지막에 reduce로 한 번에 다 더해준다는 것을 제외하면 괜찮은 것 같다.

Solution 풀이

function solution(arr) {
  let answer = 'NO',
    flag = 0;
  let total = arr.reduce((a, b) => a + b, 0);
  let n = arr.length;
  function DFS(L, sum) {
    if (flag) return;
    if (L === n) {
      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));

부분집합 구하기 문제에서 내가 푼 방식이랑 더 유사한 것 같다. (그 문제와 이 문제의 내 풀이 / Solution 풀이 방식이 반대로 바뀐 것 같다 ㅋㅋ)
하지만 이 문제에서는 부분집합 구하기 문제에서 내가 푼 방식이 오히려 효율적인데, 이는 파라미터로 배열을 넘기는 것이 아니라, sum이라는 변수를 넘기기 때문이다!