DFS - 합이 같은 부분집합

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

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

둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주 어진 원래의 집합이 되어야 합니다.

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

 

▣ 입력설명

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000 이하입니다.

 

▣ 출력설명

첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.

 

▣ 입력예제 1

6 1 3 5 6 7 10

 

▣ 출력예제 1

YES

---

해석

재귀함수를 활용해서 부분집합을 구한 후, 부분집합을 제외한 나머지 집합과의 합을 비교해서 같은 것이 발견됬다면 "YES"를 출력하고, 발견되지 않으면 "NO"를 출력하면 된다.

재귀를 이용해서 부분집합을 구하는 문제의 연장선이다.

let [n, arr] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
n = Number(n);
arr = arr.split(' ').map(Number);
let ret = 0;

function solve(idx, t) {
  if (idx === n) {
    const filtered = arr.filter((n) => !t.includes(n));
    const a = filtered.reduce((acc, cur) => acc + cur, 0);
    const b = t.reduce((acc, cur) => acc + cur, 0);
    if (a === b) ret = 1;
    return;
  } else {
    t.push(arr[idx]);
    solve(idx + 1, t);
    t.pop();
    solve(idx + 1, t);
  }
}

function solution() {
  solve(0, []);
  if (ret) return 'YES';
  return 'NO';
}

console.log(solution());

 

위의 코드도 정답이 출력되지만 케이스를 찾은 이후에도 재귀함수가 호출되므로 비용이 많이 들 수 있다.

flag 변수를 활용해서 케이스가 발견된다면 재귀함수를 호출하지 않고 곧바로 리턴하도록 구현할 수 있다.

let [n, arr] = require('fs').readFileSync('input.txt').toString().trim().split('\n');
n = Number(n);
arr = arr.split(' ').map(Number);
let total = arr.reduce((acc, cur) => acc + cur, 0);
let ret = 'NO';
let flag = 0;

function solve(idx, sum) {
  if (flag) return;
  if (idx === n) {
    if (total - sum === sum) {
      flag = 1;
      ret = 'YES';
    }
    return;
  } else {
    solve(idx + 1, sum + arr[idx]);
    solve(idx + 1, sum);
  }
}

function solution() {
  solve(0, 0);
  return ret;
}

console.log(solution());