Pattern GuideBacktracking

Backtracking

"Try every path. Undo when it fails. Try the next."

8 min read Expert Time: O(branch^depth)
01
CORE INTUITION

Explore → Undo → Explore

Imagine you're in a maze with a fork in every corridor. At each fork you pick a direction and keep walking. Hit a dead end? You don't teleport out — you walk back to the last fork you remember, and try the next unexplored corridor instead. That's backtracking, in full.

Backtracking is a systematic way to explore all candidate solutions and abandon ("prune") paths the instant they become invalid — a wall in the maze, a queen already under attack, brackets that can never balance. You don't wait to hit the actual dead end; you stop walking a doomed corridor as soon as you can tell it's doomed. It's depth-first search on a decision tree with early termination.

CHOOSE — Make a decision (place a queen, pick a parenthesis)

EXPLORE — Recurse with the new state

PRUNE — Skip invalid branches early

UNCHOOSE — Undo the decision and try the next option

02
VISUAL

DFS on a Decision Tree

Start

abcdefghi
03
GOLDEN TEMPLATE

Choices → Constraints → Goal

The Mental Checklist

CHOICES

What options do I have at each step?

CONSTRAINTS

Which choices are invalid? Prune them!

GOAL

When do I record a solution and return?

Every backtracking problem below is the exact same skeleton wearing different clothes. Learn this shape once:

backtrack.js
1
function backtrack(state, choices) {
2
if (isSolution(state)) {
3
record(state);
4
return;
5
}
6
for (const choice of choices) {
7
if (!isValid(choice, state)) continue; // PRUNE
8
9
apply(choice, state); // CHOOSE
10
backtrack(state, nextChoices(state)); // EXPLORE
11
undo(choice, state); // UNCHOOSE
12
}
13
}
04
CLASSIC #1

Subsets (Power Set)

Simplest Backtracking There Is

The simplest backtracking: every element is either taken or skipped. Record every intermediate state — there's no "wrong" subset, so nothing needs pruning.

subsets.js
1
function subsets(nums) {
2
const result = [];
3
4
function backtrack(start, curr) {
5
result.push([...curr]); // every prefix is a subset
6
for (let i = start; i < nums.length; i++) {
7
curr.push(nums[i]); // choose
8
backtrack(i + 1, curr); // explore
9
curr.pop(); // unchoose
10
}
11
}
12
13
backtrack(0, []);
14
return result;
15
}

Complexity: 2 choices (take/skip) per element, N elements → O(2^N) subsets, each costing O(N) to copy — O(N · 2^N) total.

05
CLASSIC #2

Permutations

Order Matters Now

Unlike subsets, every element must appear exactly once, but order matters — [1,2] and [2,1] are different results. Track which indices are already used to prune re-selecting them.

permutations.js
1
function permute(nums) {
2
const result = [];
3
const used = new Array(nums.length).fill(false);
4
5
function backtrack(curr) {
6
if (curr.length === nums.length) {
7
result.push([...curr]);
8
return;
9
}
10
for (let i = 0; i < nums.length; i++) {
11
if (used[i]) continue; // PRUNE: already in this permutation
12
used[i] = true; // CHOOSE
13
curr.push(nums[i]);
14
backtrack(curr); // EXPLORE
15
curr.pop(); // UNCHOOSE
16
used[i] = false;
17
}
18
}
19
20
backtrack([]);
21
return result;
22
}

Complexity: N choices, then N-1, then N-2... → O(N!) permutations, each costing O(N) to copy — O(N · N!) total.

06
CLASSIC #3

Combination Sum

Prune by Running Total

Find every combination of candidates that sums exactly to a target — the same candidate can be reused unlimited times. The prune is arithmetic: the moment the running sum overshoots the target, that whole branch is dead.

combination_sum.js
1
function combinationSum(candidates, target) {
2
const result = [];
3
4
function backtrack(start, curr, remaining) {
5
if (remaining === 0) {
6
result.push([...curr]);
7
return;
8
}
9
if (remaining < 0) return; // PRUNE: overshot the target
10
11
for (let i = start; i < candidates.length; i++) {
12
curr.push(candidates[i]); // CHOOSE
13
backtrack(i, curr, remaining - candidates[i]); // EXPLORE (i, not i+1: reuse allowed)
14
curr.pop(); // UNCHOOSE
15
}
16
}
17
18
backtrack(0, [], target);
19
return result;
20
}

Key detail: recursing with i (not i + 1) is what allows reusing the same candidate again — passing i + 1 instead turns this into Combination Sum II (each candidate used at most once).

07
CLASSIC #4

Generate Parentheses

The Pruning Rule

The constraint is simple: we can add '(' if open < n, and ')' if close < open. This ensures well-formed parentheses.

generate_parenthesis.js
1
function generateParenthesis(n) {
2
const result = [];
3
4
function backtrack(curr, open, close) {
5
if (curr.length === 2 * n) {
6
result.push(curr);
7
return;
8
}
9
if (open < n) backtrack(curr + '(', open + 1, close);
10
if (close < open) backtrack(curr + ')', open, close + 1);
11
}
12
13
backtrack('', 0, 0);
14
return result;
15
}

Complexity: the count of valid sequences is the N-th Catalan number, C(N) = (2N choose N) / (N + 1) — much smaller than the naive 2^(2N) because most branches get pruned early.

08
CLASSIC #5

N-Queens

Place N queens on an N×N board so no two attack each other. The classic backtracking showcase: one queen per row, prune by column + diagonal conflicts.

n_queens.js
1
function solveNQueens(n) {
2
const result = [];
3
const board = Array(n).fill('.'.repeat(n));
4
5
function isSafe(row, col) {
6
for (let i = 0; i < row; i++) {
7
// Same column
8
if (board[i][col] === 'Q') return false;
9
// Diagonal left
10
const diagLeft = col - (row - i);
11
if (diagLeft >= 0 && board[i][diagLeft] === 'Q') return false;
12
// Diagonal right
13
const diagRight = col + (row - i);
14
if (diagRight < n && board[i][diagRight] === 'Q') return false;
15
}
16
return true;
17
}
18
19
function backtrack(row) {
20
if (row === n) { result.push([...board]); return; }
21
for (let col = 0; col < n; col++) {
22
if (!isSafe(row, col)) continue;
23
// CHOOSE
24
board[row] = board[row].slice(0, col) + 'Q' + board[row].slice(col + 1);
25
backtrack(row + 1);
26
// UNCHOOSE
27
board[row] = '.'.repeat(n);
28
}
29
}
30
31
backtrack(0);
32
return result;
33
}

Key insight: The isSafe check is the pruning step. Without it, we'd generate all N^N board arrangements — with it, we only explore valid partial solutions.

09
RECOGNITION

How to Spot This Pattern

🔎 "Generate all..." combinations, permutations, or subsets.

🔎 Constraints look tiny — n ≤ ~20 is a strong tell that exponential search is expected.

🔎 "Find all valid ways to place / arrange / partition..."

Named problems: Subsets · Permutations · Combination Sum · Palindrome Partitioning · N-Queens · Sudoku Solver · Word Search

10
PITFALLS

Common Mistakes

Forgetting to Copy the Path

result.push(path) stores a reference to the same array you keep mutating — every recorded "solution" ends up identical (usually empty) by the time you're done. Always push a copy: result.push([...path]).

Pruning Too Late

Checking validity inside the recursive call (after already choosing and recursing) wastes an entire function call and stack frame on a branch you already know is dead. Check before you recurse, so invalid choices are skipped, not entered.

Mutating Shared State Without Undo

Every CHOOSE needs a matching UNCHOOSE. Forgetting to pop/reset after the recursive call returns leaves stale state bleeding into sibling branches — the classic symptom is "it works for the first path, then everything after is wrong."

11
PRACTICE

Ready to Practice?

Subsets (Power Set)Medium
PermutationsMedium
Combination SumMedium
N-QueensHard

"Backtracking = DFS + pruning + undo."