[인프런 섹션8] 합이 같은 부분집합 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션8] 합이 같은 부분집합 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-29

1. (집합의 합 === 전체 집합의 합 - 집합의 합) 인지 확인하여 true면 "YES", false면 "NO"

• 한 번이라도 조건을 만족하면 전체종료

if (n >= arr.length) {
  let sum = res.reduce((a, b) => a + b, 0);
  if (su)
}

2. 부분집합의 합 구하는 2가지 방법

• 방법 1. res.push(), res.pop()

let res = [];
let total = arr.reduce((a, b) => a + b, 0);

function DFS(n) {
  if (n >= arr.length) {
    let sum = res.reduce((a, b) => a + b, 0);
    if (sum === total - sum) return "YES"
  }
  res.push(arr[n]);
  DFS(n+1);
}

• 방법 2. sum += n, sum -= n

let sum = 0;
let total = arr.reduce((a, b) => a + b, 0);

function DFS(n) {
  if (n >= arr.length) {
    if (sum === total - sum) return "YES";
  }
  sum += arr[n];
  DFS(n+1);
  sum -= arr[n];
  DFS(n+1);
}

3. 한 번이라도 조건을 만족하면 전체종료하는 방법

• return flag 생성
• DFS 내부에서 flag = true/false
• DFS 외부에서 flag 값에 따라 YES/NO 출력

let flag = false;

function DFS (n) {
  if (flag) return;
  else {}
}

DFS(0);
console.log(flag ? "YES" : "NO");

✍️소스코드

2021-06-29

let arr = [1, 3, 5, 6, 7, 10];
let total = arr.reduce((a, b) => a + b, 0);
let sum = 0;
let flag = false;

function DFS(n) {
  if (flag) return;
  if (n >= arr.length) {
    if (sum === total - sum) flag = true;
    return;
  }
  sum += arr[n];
  DFS(n + 1);
  sum -= arr[n];
  DFS(n + 1);
}

DFS(0);
console.log(flag ? "YES" : "NO");