[DFS]합이 같은 부분집합

문제

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

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

 

문제풀이_묶음 기준

---

• 묶을 경우와 묶지 않을 경우 두 개로 나눠 다음 레벨로 이동
• depth를 넘어설 경우 탐색 종료 및 나뉜 두 집합을 비교

코드

function solution(d, n) {
  let answer = 'NO';
  let flag = 0;
  let check = Array.from({length: d + 1}, () => 0);

  function DFS(v) {
    if(v === d + 1) {
      if(flag) return;
      let tmp1 = 0; //1번 집합의 합
      let tmp2 = 0; //2번 집합의 합
      for(let i = 1; i < check.length; i++) {
        if(check[i] === 1) tmp1 += n[i-1];
        else tmp2 += n[i-1];
      }
      if(tmp1 === tmp2) {
        answer ='YES';
        flag = 1;
      }
    }
    else {
      check[v] = 1; //1번 집합에 묶을 경우
      DFS(v + 1);
      check[v] = 2; //2번 집합에 묶을 경우
      DFS(v + 1);
    }
  }
  DFS(1);
  return answer;
}

let depth = 6;
let nums = [1, 3, 5, 6, 7, 10];

console.log(solution(depth, nums));

 

문제풀이_합 기준

---

• 합하는 경우와 합하지 않는 경우로 나눠 진행
• 합하든 합하지 않든 간에 레벨은 무조건 증가
• 탐색이 종료되면 합한 값과 합하지 않은 나머지 값(여집합의 값)을 비교

코드

function solution(arr) {
  let answer = 'NO';
  let flag = 0;
  let total = arr.reduce((a, b) => a + b, 0); //모든 원소의 합
  let n = arr.length;

  function DFS(level, sum) {
    if(flag) return;
    if(level === n) {
      if(sum === (total - sum)) { //여집합 원소 합과의 비교
        answer = 'YES';
        flag = 1 ;
      }
    }
    else {
      DFS(level + 1, sum + arr[level]); //합하는 경우
      DFS(level + 1, sum); //합하지 않고 다음 레벨로 넘어가는 경우
    }
  }
  DFS(0, 0); //레벨과 축적 합
  return answer;
}

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