[알고리즘 공부]DFS정리

이 문서는 programmers level2 타겟넘버 를 기준으로 만들었습니다.

DFS 정리

const numbers = [1, 2, 3, 4] 

const target = 6

dfs: 진행이 가능하다면 계속 진행

function solution(numbers, target) {
  let answer = 0;
  const dfs = (idx = 0, sum = 0) => {
    if (idx === numbers.length) {
      if (sum === target) answer++;
      return;
    }
    dfs(idx + 1, sum + numbers[idx]);
    dfs(idx + 1, sum - numbers[idx]);
  };
  dfs();
  return answer;
}

원시객체(idx,sum) 은 sideEffect 가 발생하지 않는다.

numbers .length = 4

step 1

i = 0, sum = 0

dfs (0+1, 0+1) A

dfs (0+1, 0-1) B

step 2

A sum = 1

​ dfs(1+1, 1+ 2 ) C

​ dfs(1+1, 1- 2 ) D

B sum = -1

​ dfs(1+1, -1+ 2 ) E

​ dfs(1+1, -1- 2 ) F

step 3

i =2

C

​ dfs(2+1, 3+3 )

​ dfs(2+1, 3- 3 )

D

​ dfs(2+1, -1+3 )

​ dfs(2+1, -1-3 )

E

​ dfs(2+1, 1+3 )

​ dfs(2+1, 1-3 )

F

​ dfs(2+1, -3+ 3 )

​ dfs(2+1, -3- 3 )