[学習アルゴリズム]DFSのクリーンアップ


この文書は、プログラマレベル2目標番号に基づいています.

クリア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 )