Backtracking
Walk into a maze with a piece of chalk. When you hit a dead end, step back to the last fork and try the next turn, never walking the same dead end twice. Backtracking explores choices the same way, undoing each step so every option gets exactly one visit.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
Combination Sum
or try
2–4 different numbers from 2 to 9, then | and a target from 1 to 10.Sort the candidates. Start with an empty path. You need 7.Step 1 of 20. Sorted candidates 2, 3, 6, 7. Path empty. Need 7. Nothing found yet.
Step 1 of 20
solution.ts▶ marks the line running now
function combinationSum(candidates: number[], target: number): number[][] {
const result: number[][] = [];
const path: number[] = [];
candidates.sort((a, b) => a - b);
function dfs(start: number, remaining: number) {
if (remaining === 0) {
result.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
path.push(candidates[i]);
dfs(i, remaining - candidates[i]);
path.pop();
}
}
dfs(0, target);
return result;
}
4 · Your turn
0 of 2 problems solved
- Medium01
Combination Sum
The one you just watched. Write it from memory.
- Medium02
Word Search
Same try-and-undo walk, stepping to neighbour cells.