[学習アルゴリズム]DFSのクリーンアップ
1117 ワード
この文書は、プログラマレベル2目標番号に基づいています.
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 )
クリア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 )
Reference
この問題について([学習アルゴリズム]DFSのクリーンアップ), 我々は、より多くの情報をここで見つけました https://velog.io/@eamon3481/dfs-정리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol