Master the choose-explore-unchoose backtracking pattern to generate permutations, combinations, and subsets.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
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!