Backtracking

Interviewer cue: “generate all …”, “find every way to …”, or “place these pieces so that no two conflict” — backtracking is depth-first search over a decision tree of partial choices, where you undo a choice the moment it stops being viable and try the next one instead.

What you’ll learn

The choose / explore / unchoose framework — three lines that show up in almost every backtracking solution.
How a backtracking algorithm maps directly onto a decision tree.
Pruning: skipping entire branches early instead of exploring them and failing later.
Runnable Permutations and N-Queens solutions built on the same template.

The cue

The problem asks for all solutions, or any solution, to a constraint puzzle: all permutations, all subsets, all valid boards, all ways to partition — LC 46, 78, 51, 131, 37.
The answer is a sequence of choices, and a choice made now restricts what is legal later. That coupling is what rules out a greedy or a DP over indices.
Constraints are tiny — n <= 8, n <= 20, a 9×9 grid. Exponential output is expected, and the small bound is the problem telling you so.
You can describe a partial solution and test whether it is still viable. If you can prune, backtracking is usually the intended answer; if you cannot, it degenerates to brute force.

The reframe: backtracking is DFS over a decision tree you never build. Each level is one decision, each branch one option, and the “un-choose” step is what lets a single shared path serve the whole tree instead of copying state per branch.

Reach for something else when you only need how many solutions rather than the solutions themselves (that is usually DP — counting does not need enumeration), when subproblems overlap so results can be cached, or when a greedy choice is provably safe. Backtracking is the tool of last resort, and saying that out loud before writing it is the right framing.

The pattern

permutations_backtrack.py

def permutations(nums):
    results = []
    path = []
    used = [False] * len(nums)
 
    def backtrack():
        if len(path) == len(nums):
            results.append(path[:])      # snapshot -- path keeps mutating after this
            return
        for i, num in enumerate(nums):
            if used[i]:
                continue
            path.append(num)             # 1. CHOOSE
            used[i] = True
            backtrack()                  # 2. EXPLORE
            path.pop()                    # 3. UNCHOOSE
            used[i] = False
 
    backtrack()
    return results
 
 
print(permutations([1, 2, 3]))

Three steps, every time: choose an option and record it, explore by recursing one level deeper, then unchoose — undo that exact choice so the next iteration of the loop starts from a clean slate.

Visual intuition

Backtracking is a tree walk where the state is shared and undone rather than copied. Here is that tree for the simplest possible case:

recursionChoose, explore, un-choosethe three-line skeleton

call stack

[]

1def subsets(nums):2    out, path = [], []3    def go(i):4        if i == len(nums):5            out.append(path[:])      # copy! path keeps mutating6            return7        path.append(nums[i])         # branch 1: include8        go(i + 1)9        path.pop()                   # UNDO — this is the backtrack10        go(i + 1)                    # branch 2: exclude11    go(0)12    return out

i0path[]

callStart with an empty path and index 0. Every node in this tree is a decision about one element: include it or do not.

1/39

Every backtracking solution is these three steps around a recursive call. The un-choose is the step people forget, and its absence is silent: the code still runs, it just produces garbage.

How it works: the decision tree

diagram Backtracking decision tree: permutations of [1, 2, 3] (partial) mermaid

  graph TD
    R["[]"] --> A["[1]"]
    R --> B["[2]"]
    R --> C["[3]"]
    A --> A1["[1, 2]"]
    A --> A2["[1, 3]"]
    B --> B1["[2, 1]"]
    B --> B2["[2, 3]"]
    C --> C1["[3, 1]"]
    C --> C2["[3, 2]"]
    A1 --> A1a["[1, 2, 3]"]
    B1 --> B1a["[2, 1, 3]"]
    C1 --> C1a["[3, 1, 2]"]

Every edge downward is a choose. When a branch bottoms out (a full permutation) or runs out of valid options, the algorithm walks back up — that’s the unchoose — and tries the next sibling edge. The full tree for 3 elements has $3! = 6$ leaves; this diagram shows enough of it to see the shape.

Worked example: N-Queens

Place n queens on an n x n board so no two attack each other — no shared row, column, or diagonal. Track attacked columns and diagonals with sets so each placement check is $O(1)$ , pruning invalid branches instantly instead of discovering the conflict later.

n_queens.py

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()   # r - c is constant along a "/" diagonal
    diag2 = set()   # r + c is constant along a "\" diagonal
    board = []       # board[r] = column index of the queen placed in row r
 
    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
 
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue                       # PRUNE: this column is attacked, skip it
 
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            board.append(col)                  # 1. CHOOSE
 
            backtrack(row + 1)                 # 2. EXPLORE
 
            board.pop()                        # 3. UNCHOOSE
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
 
    backtrack(0)
    return solutions
 
 
solutions = solve_n_queens(4)
print("solutions for 4-queens:", len(solutions))
print("first solution (column per row):", solutions[0])

Dry run

4-Queens, the first two rows. board[r] is the column of the queen in row r; the three sets make each legality test $O(1)$ .

row	column tried	verdict	why
0	0	place → `[0]`	board is empty, everything is legal
1	0	prune	column 0 taken
1	1	prune	`row − col = 0` collides with the queen at (0,0) on a `/` diagonal
1	2	place → `[0,2]`	legal — recurse into row 2, which finds nothing and unwinds
1	3	place → `[0,3]`	legal — also fails deeper
0	1	place → `[1]`	after fully unwinding row 0’s first branch
1	0,1,2	prune ×3	column, `/`, and `\` conflicts respectively
1	3	place → `[1,3]`	this branch eventually yields `[1,3,0,2]` ✓

Solutions: [1,3,0,2] and [2,0,3,1].

Pruning is the algorithm, not an optimisation. For n = 4: 17 nodes visited, 44 placements rejected against $4^4 = 256$ for brute force. At n = 8 it is 2,057 nodes against $8^8 = 16{,}777{,}216$ — four orders of magnitude, entirely from testing legality before recursing rather than checking a completed board.
The three sets are chosen so the test is $O(1)$ . r − c is constant along a / diagonal and r + c along a \ one, so a conflict is a set lookup rather than a scan over placed queens. Choosing a representation that makes the prune cheap is most of the design work.
Every mutation is undone in reverse order — board.pop() then all three remove calls. Miss one and the constraint leaks into sibling branches, which silently loses solutions rather than producing wrong ones. The symptom is “my answer has too few results”.
solutions.append(board[:]) copies. board keeps mutating after the append; storing the reference gives a list of identical empty lists — the same bug as in every other backtracking problem on this page.

Complexity

Backtracking explores a decision tree that’s exponential in the worst case — $O(n!)$ for permutations, roughly $O(n^n)$ before pruning for N-Queens. Pruning doesn’t change the worst-case bound, but it’s what makes these algorithms fast enough to actually run: N-Queens with column/diagonal sets finishes instantly for boards where a naive “place all, then check” version would time out.

When to use it

“Generate all …” / “find every way to …” — permutations, combinations, subsets (next lesson).
Constraint satisfaction — N-Queens, Sudoku Solver: place pieces one at a time, backing out the moment a constraint is violated.
Path search with undo — Word Search: mark a grid cell visited while exploring from it, then un-mark it before trying a different path.

If you only need to know whether a valid arrangement exists (not all of them), the same shape works — just return True the instant one is found instead of collecting every result.

The variant map

Problem	The choice at each level	The prune
LC 46 Permutations	which unused element comes next	`used[i]`
LC 47 Permutations II	same, with duplicates	sort, then skip `nums[i] == nums[i-1] and not used[i-1]` — see Permutations
LC 78 / 90 Subsets	take or skip each element	a `start` index, so earlier elements are never revisited
LC 39 / 40 Combination Sum	which candidate to add	`remaining - candidate < 0` prunes the branch immediately
LC 51 / 52 N-Queens	which column in this row	three sets: `cols`, `r − c`, `r + c`
LC 37 Sudoku Solver	which digit in this cell	row / column / box sets; return `True` on the first solution rather than collecting
LC 79 Word Search	which neighbour to step to	mark the cell, recurse, un-mark — the grid is the visited set
LC 131 Palindrome Partitioning	where to cut	the prefix must be a palindrome; precompute a table to make the test $O(1)$
LC 22 Generate Parentheses	`(` or `)`	`open < n`, and `close < open`
LC 17 Letter Combinations	which letter for this digit	none — the tree is already exactly the answer set
Any “does one exist”	—	return `True` up the stack the instant one is found; do not enumerate the rest

Pitfalls

Storing the path instead of a copy. results.append(path) stores a reference that later pop() calls empty. path[:] (or list(path)) snapshots it. The most common bug in the whole topic.
An unmatched choose/unchoose. Every mutation before the recursive call needs its exact inverse after it — including all of them when a step touches several structures, as N-Queens’ three sets do. A missed undo leaks constraints into sibling branches and silently loses solutions.
Pruning after recursing instead of before. Checking legality at the leaf still gives the right answer and destroys the performance: that is the difference between 17 nodes and 256.
Using a start index for permutations, or used[] for subsets. start prevents revisiting earlier elements, which is right for combinations and wrong for permutations.
Duplicate handling without sorting. The skip rule compares neighbours, so equal values must be adjacent first.
Collecting every solution when one suffices. Sudoku and “can it be done” variants should return True immediately; enumerating the rest can be exponentially more work for the same answer.
Forgetting the recursion limit. Deep decision trees (Sudoku, Word Search on a big grid) can approach CPython’s ~1000 frames.

Interview follow-ups

They ask	What they’re checking	The answer
“What is the complexity?”	Honesty about exponentials	Bounded by the size of the decision tree: $O(n!)$ for permutations, $O(2^n)$ for subsets, and for N-Queens $O(n!)$ rather than $O(n^n)$ because each row picks an unused column. Pruning changes the constant dramatically but not the class
“Then why bother pruning?”	Whether you can quantify it	Because the class is not the runtime. 4-Queens: 17 nodes visited versus 256 brute-force placements; 8-Queens: 2,057 versus 16.7 million. Legality tested before recursing is the whole difference
“Why the copy in `results.append(path[:])`?”	The classic bug	`path` is one list mutated throughout the traversal. Appending it stores an alias that the un-choose step then empties, leaving a list of identical empty lists
“Make N-Queens’ check $O(1)$ ”	Data-structure choice	Three sets: occupied columns, `r − c` (constant along `/`), `r + c` (constant along `\`). Scanning the placed queens instead is $O(n)$ per test and turns the prune into the bottleneck
“You only need one solution, not all”	Reading the requirement	Return `True` up the stack the moment a leaf validates, and propagate it — `if backtrack(...): return True`. Sudoku is the standard case, and enumerating everything there is exponentially wasteful
“How is this different from DFS?”	Precision	It is DFS, over a decision tree that is generated rather than stored, with an explicit undo so one shared state serves every branch. The un-choose step is the only structural difference
“Could DP solve this instead?”	Knowing the boundary	Only if you need a count or an optimum rather than the solutions themselves, and subproblems overlap. Enumerating $n!$ objects cannot beat $O(n!)$ — no cache helps when the output is the bottleneck
“Reduce the branching factor”	Practical optimisation	Order the choices to fail fast — in Sudoku, fill the cell with the fewest candidates first (most-constrained-variable). Same tree, radically fewer nodes explored

Practice — real LeetCode problems

Three shapes of the same skeleton. The first has a fixed depth and no pruning, the second adds an undo on a mutable grid, and the third adds constraint sets that make the pruning cheap.

LC 17 — Letter Combinations of a Phone Number · Medium

Problem. Given a string of digits 2-9, return all letter combinations the number could spell, using the standard phone keypad. Return them in any order.

Constraints. 0 <= len(digits) <= 4, digits are 2 through 9 only.

Examples. "23" gives ["ad","ae","af","bd","be","bf","cd","ce","cf"] · "" gives [] · "2" gives ["a","b","c"]

Editorial · approach, complexity, follow-ups

The purest backtracking template there is: fixed depth, no pruning, no constraints. The output is sorted before printing only so the grader can compare it — LeetCode accepts any order.

Time $O(4^n \cdot n)$ — at most 4 letters per digit, and joining each word costs $O(n)$ . Space $O(n)$ for the path, excluding the output.

Empty input returns [], not [""]. This is the single most-failed test case on the problem. Zero digits spell zero words, not one empty word — and the bare recursion would happily record the empty path.
path.pop() after the recursive call is what makes the shared path list safe. Forgetting it leaks letters into sibling branches.
7 and 9 have four letters, 2-6 and 8 have three. Hard-coding three breaks "79", which is why it is in the tests.
Appending path[:] versus "".join(path) — joining copies anyway, so strings are safe to store. When the answer is a list, you must copy explicitly; that trips people on the next problem.

Follow-ups you should expect: “Iteratively?” — build the answer level by level, or use itertools.product(*[pad[d] for d in digits]), which is the one-liner worth mentioning after you have shown the manual version. “Return only combinations in a dictionary?” — pass a trie down and prune the moment a prefix is impossible; that is the T9 autocomplete question. “Digits 1 and 0?” — they map to nothing, so the answer is empty. “10 digits?” — $4^{10}$ is a million words, so you would stream them with a generator rather than materialise a list.

LC 79 — Word Search · Medium

Problem. Given a grid of characters and a word, return True if the word can be built from sequentially adjacent cells (horizontal or vertical neighbours). The same cell may not be used twice.

Constraints. 1 <= rows, cols <= 6, 1 <= len(word) <= 15, letters are alphanumeric.

Examples. With [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]: "ABCCED" gives True · "SEE" gives True · "ABCB" gives False

Editorial · approach, complexity, follow-ups

Backtracking on a grid. The difference from the flood-fill DFS in the graph section is the undo: flood fill marks a cell visited forever, because it only cares whether a region is reachable. Here a cell that fails on one path must be available to a different path, so the mark has to be temporary.

Time $O(rc \cdot 3^L)$ where $L$ is the word length — after the first step only three directions are worth trying, since the fourth is where you came from. Space $O(L)$ for the recursion.

The mark-and-restore is the whole problem. Without the mark, "ABCB" returns True by bouncing between the B and the C. Without the restore, the second and later starting cells search a board full of #.
Base cases before bounds arithmetic. Checking i == len(word) first means a full match never needs the cell to exist.
"A" returns True — a one-character word matches immediately, and the success check must fire before any neighbour is examined.
"ABCESEEEFS" returns False on this board. It is a real path on the common variant board that has E at row 1 column 2 — here that cell is a C, so the path dies. A good reminder to read the grid you were actually given.
Restoring word[i], not the original character, is safe only because the cell matched word[i] to get here. That is a small proof worth having ready.

Follow-ups you should expect: “Search many words at once (LC 212)?” — build a trie of the words and walk the grid once against the trie; running this solution per word is far too slow. “Prune early?” — if the board’s letter counts cannot cover the word, fail immediately; also search from whichever end of the word is rarer on the board. “Diagonals allowed?” — eight directions instead of four. “Reuse allowed?” — drop the marking, and note the search may then not terminate without a depth bound. “Return the path?” — thread a list of coordinates through the recursion.

LC 51 — N-Queens · Hard

Problem. Place n queens on an n by n board so that no two attack each other. Return every distinct solution as a list of board strings, using "Q" and ".".

Constraints. 1 <= n <= 9.

Examples. n = 4 has 2 solutions · n = 1 has 1 · n = 2 and n = 3 have none

Editorial · approach, complexity, follow-ups

The classic constraint-satisfaction backtrack, and the reason it is a Hard is the encoding, not the recursion.

Two observations collapse the search space:

One queen per row. Any valid board has exactly one queen per row, so a partial solution is a list of columns and the recursion depth is n — not $n^2$ cells to consider.
Diagonals are arithmetic. Every cell on a / diagonal shares r + c; every cell on a \ diagonal shares r - c. So three sets replace what would otherwise be an $O(n)$ scan per candidate.

Without pruning there are $n!$ column permutations to test; with these three sets the illegal branches die at the moment they are created, which is what makes n = 9 instant.

Time exponential — bounded by $n!$ but hugely pruned in practice. Space $O(n)$ for the sets and path, plus the output.

Undo everything you did, and note the code undoes in reverse order. Leaving one set dirty silently loses solutions rather than crashing, which is the worst kind of bug.
n = 2 and n = 3 have no solutions, and the answer is an empty list, not an error. Those two are the reason the counts start [1, 0, 0, 2, ...].
The counts 1, 0, 0, 2, 10, 4, 40 for n = 1..7 are worth recognising — the non-monotonic dip at n = 6 surprises people and is a good self-check.
discard versus remove — either works here since the value is definitely present; discard just will not mask an ordering bug with a KeyError.

Follow-ups you should expect: “Only the count (LC 52)?” — identical search, increment a counter instead of building boards, and you can then use bitmasks: cols, diag and anti as integers, with the available squares computed as ~(cols | diag | anti). That is the fastest known formulation and a strong signal in an interview. “Find just one solution?” — return as soon as the first is complete. “Symmetry?” — restrict the first row to the left half and mirror the results, roughly halving the work. “Very large n?” — constructive formulas exist for placing n non-attacking queens; enumerating all solutions is intractable well before n = 30.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

9 problems

0 easy6 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

22Generate ParenthesesmediumNeetCode 150LeetCode Top Interview 150
39Combination SummediumBacktracking that allows reusing the same candidateNeetCode 150Blind 75LeetCode Top Interview 150
40Combination Sum IImediumNeetCode 150
46PermutationsmediumThe exact template aboveNeetCode 150LeetCode Top Interview 150
77CombinationsmediumChoose `k` of `n`, using a `start` index instead of a `used` arrayLeetCode Top Interview 150
79Word SearchmediumDFS + backtracking on a grid, marking and un-marking visited cellsNeetCode 150Blind 75LeetCode Top Interview 150
37Sudoku SolverhardBacktracking with row/column/box constraint pruning
51N-QueenshardPruning with column/diagonal sets, as aboveNeetCode 150
52N-Queens IIhardLeetCode Top Interview 150

Self-check

pch.quizTag Backtracking — self-check

What are the three steps, and which one makes backtracking different from plain DFS?

pch.quizShowAnswer

B — Choose, explore, un-choose — the un-choose is what lets one shared path serve the whole tree instead of copying state per branch — Backtracking IS depth-first search over a decision tree that is generated rather than stored. The explicit undo is the only structural addition.
For 4-Queens, pruning visits 17 nodes against 256 brute-force placements. What does that tell you about the complexity class?

pch.quizShowAnswer

B — Nothing — the class stays exponential; pruning changes the constant, and at n = 8 that constant is 2,057 nodes versus 16.7 million — Being able to say both halves — same class, radically different runtime — is more useful than either alone, and it is why 'exponential' is not a reason to skip the pruning.
Why does N-Queens track `r − c` and `r + c` in sets?

pch.quizShowAnswer

B — Because r − c is constant along a `/` diagonal and r + c along a `\` one, so a conflict test is an O(1) set lookup instead of an O(n) scan over placed queens — Choosing a representation that makes the prune cheap is most of the design work. A scan would make the legality test the bottleneck it was meant to remove.
You forget one of the three `remove` calls in the un-choose step. What is the symptom?

pch.quizShowAnswer

B — Solutions go missing — the stale constraint leaks into sibling branches and rejects placements that were legal, so the count is too LOW rather than wrong — Too-few-results is the tell for a missing undo; too-many is usually a missing prune. Knowing which direction the bug pushes the count narrows the search immediately.
Sudoku asks for one valid board, not all of them. What changes?

pch.quizShowAnswer

B — Return True up the stack the moment a leaf validates, and propagate it (`if backtrack(...): return True`) — enumerating the rest can be exponentially more work for the same answer — Same skeleton, different return contract. The 'does one exist' variant of any of these problems takes this shape.
When should you NOT reach for backtracking?

pch.quizShowAnswer

B — When you only need a count or an optimum and the subproblems overlap — that is DP; enumeration is wasted when the answer is a single number — Counting rarely needs enumeration. Backtracking is the tool of last resort, and framing it that way before writing it is the right instinct.

Recall card

Cue — enumerate all (or find any) solutions to a constraint problem; the answer is a sequence of coupled choices; constraints are tiny (n ≤ 8–20).
The skeleton — choose → explore → un-choose, with every mutation undone in reverse.
Snapshot on record — results.append(path[:]), never path.
Prune before recursing, not at the leaf. That is where all the savings are: 4-Queens visits 17 nodes instead of 256; 8-Queens 2,057 instead of 16.7 million.
Make the prune $O(1)$ — N-Queens uses cols, r − c, r + c sets; Sudoku uses row/col/box sets; Word Search mutates the grid itself.
start index for combinations, used[] for permutations. Mixing them up is the standard structural error.
One solution needed? Return True and propagate — do not enumerate the rest.
Cost — the size of the decision tree: $O(n!)$ permutations, $O(2^n)$ subsets. Pruning changes the constant, never the class.
Order choices to fail fast (most-constrained variable) when the tree is still too big.

Recap

Choose, explore, unchoose — the three-line skeleton behind every backtracking solution.
Backtracking is DFS over a decision tree; leaves are complete valid (or invalid) candidates.
Pruning checks partial validity immediately, skipping entire subtrees instead of building and rejecting them.
Worst case is exponential ( $O(n!)$ , $O(n^n)$ , …) — pruning doesn’t change that bound, but makes real inputs tractable.

Next: Subsets and Combinations — the include/exclude version of this same decision tree, generating all $2^n$ subsets.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading