이진트리DFS

선택했냐 안했냐로 트리를 구성하면 쉽게 풀수있다.

합이 같은 부분집합

  let answer = "NO";
  let sum = arr.reduce((a, b) => a + b);
  function DFS(number, reducer) {
    
    if (answer === "YES" || number === arr.length) {
      return;
    }

    if (sum - reducer === reducer) {
      answer = "YES";
    }
    // 포함된거
    DFS(number + 1, reducer + arr[number]);
    // 포함안된거
    DFS(number + 1, reducer);
  }
  DFS(0, 0);
  return answer;

바둑이승차

 let answer = Number.MIN_SAFE_INTEGER;
  function DFS(number, sum) {
    if (number > arr.length) {
      return;
    }
    if (sum < c) {
      answer = Math.max(sum, answer);
    }
    DFS(number + 1, sum + arr[number]);
    DFS(number + 1, sum);
  }
  DFS(0, 0);
  return answer;

중복순열

    let array = [...new Array(n)].map((_, i) => i + 1);
    function DFS(stack, depth) {
      if (depth === m) {
        console.log(stack);
        return;
      }
      for (let check = 0; check < array.length; check++) {
        DFS([...stack, array[check]], depth + 1);
      }
    }
    DFS([], 0);

최대점수구하기

  let answer = Number.MIN_SAFE_INTEGER;
  function DFS(index, sum, time) {
    if (index > ps.length || time > m) {
      return;
    }
    if (m >= time) {
      answer = Math.max(answer, sum);
    }
    DFS(index + 1, sum + ps[index], time + pt[index]);
    DFS(index + 1, sum, time);
  }
  DFS(0, 0, 0);
  return answer;

DFS cut

종료 시점을 정해주는 것. 아래 문제는 내일 리팩토링

동전교환

  let answer = Number.MAX_SAFE_INTEGER;
  function DFS(number, sum, depth) {
    if (arr.length < depth) {
      return;
    }
    if (number === 0) {
      answer = Math.min(answer, sum);
      console.log(answer);
      return;
    }
    for (let check = 0; check < arr.length; check++) {
      DFS(
        number % arr[check],
        sum + Math.floor(number / arr[check]),
        depth + 1
      );
    }
  }
  DFS(m, 0, 0);