Quick Overview
Backtracking walks a decision tree and undoes each choice on the way back out. That `unchoose` step is what lets one array serve every branch instead of copying the partial result at each of the N levels.
Backtracking is a generalized algorithmic technique that incrementally builds candidates toward a solution and abandons ("backtracks") a candidate path as soon as it determines the path cannot lead to a valid solution.
All backtracking algorithms follow the Choose -> Explore -> Unchoose pattern:
function backtrack(candidateState) {
if (isCompleteSolution(candidateState)) {
saveSolution(candidateState);
return;
}
for (const choice of availableChoices) {
if (isValidChoice(choice)) {
makeChoice(choice); // 1. Choose
backtrack(nextState); // 2. Explore (Recurse)
undoChoice(choice); // 3. Unchoose (Backtrack state!)
}
}
}
Given an array of unique numbers, return all possible subsets:
function subsets(nums) {
const result = [];
function generate(startIndex, currentPath) {
result.push([...currentPath]); // Save a copy of current subset
for (let i = startIndex; i < nums.length; i++) {
currentPath.push(nums[i]); // 1. Choose
generate(i + 1, currentPath); // 2. Explore
currentPath.pop(); // 3. Unchoose (Backtrack!)
}
}
generate(0, []);
return result;
}
console.log(subsets([1, 2]));
// Output: [ [], [ 1 ], [ 1, 2 ], [ 2 ] ]
[ ]
/ \
+1 / \ +2
[1] [2]
/
+2 /
[1, 2]
result.push(currentPath) without making a copy ([...currentPath]) stores references to the same array, which ends up empty after backtracking pops all items!Use backtracking for Sudoku, N-Queens, and permutations. Next, let's explore Binary Search!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.