Backtracking
Think of it like this
Imagine navigating a maze. At each junction, you pick a direction. If you hit a dead end, you backtrack to the last junction and try the next direction. You keep doing this until you find the exit, or exhaust all paths.
Backtracking is exactly this: explore a path until it's invalid, then undo and try another.
Maze: S → A → B → dead end
↑
S → A → C → D → exit ✓ (backtracked from B, tried C)This is different from brute force: instead of generating all possible paths and filtering, backtracking prunes paths early the moment they violate a constraint, cutting huge branches of the search tree.
The Framework: Choose → Explore → Unchoose
Every backtracking problem follows this three-step template:
function backtrack(state, choices) {
// Base case: is the current state a complete valid solution?
if (isComplete(state)) {
results.push([...state]); // save a copy (not a reference!)
return;
}
for (const choice of choices) {
if (!isValid(state, choice)) continue; // pruning: skip bad choices
// Choose
state.push(choice);
// Explore: recurse with the updated state
backtrack(state, nextChoices(state, choice));
// Unchoose: undo the choice (backtrack!)
state.pop();
}
}The undo step (state.pop()) is what makes it backtracking, not just DFS. You restore the state to what it was before this choice, allowing other paths to be explored from a clean slate.
Visualizing the Decision Tree
Generate all permutations of [1, 2, 3]:
[]
┌─────────┼─────────┐
[1] [2] [3]
┌───┐ ┌───┐ ┌───┐
[1,2][1,3][2,1][2,3][3,1][3,2]
↓ ↓ ↓ ↓ ↓ ↓
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
6 permutations = 3! ✓
Each leaf is a complete solution.4-Queens Backtracking & Pruning
Place 4 non-attacking queens on a 4x4 chessboard.
Initialize empty 4x4 board. Begin trial placement at Row 0.
function permutations(nums) {
const results = [];
function backtrack(current, remaining) {
if (!remaining.length) { results.push([...current]); return; }
for (let i = 0; i < remaining.length; i++) {
current.push(remaining[i]); // choose
backtrack(current, remaining.filter((_, j) => j !== i)); // explore
current.pop();
Subsets, Power Set
Every element has two choices: include or exclude.
nums = [1, 2, 3]
[]
┌───────────┐
exclude 1 include 1
[ ] [1]
┌──┴──┐ ┌──┴──┐
excl2 incl2 excl2 incl2
[] [2] [1] [1,2]
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
[] [3][2] [2,3][1][1,3][1,2][1,2,3]
Result: [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]function subsets(nums) {
const results = [];
function backtrack(start, current) {
results.push([...current]); // every state (including empty) is valid
for (let i = start; i < nums.length; i++) {
current.push(nums[i]); // choose
backtrack(i + 1, current); // explore (i+1 to avoid reuse)
current.pop(); // unchoose
}
}
backtrack(0, []);
return results;