Systematic trial-and-error over a decision tree: choose, explore, un-choose. Subsets, permutations, combinations, N-Queens, and Sudoku — with pruning that turns brute force into feasible.
0 of 8 lessons checked off
Introduction
What it is
Backtracking builds candidate solutions one decision at a time and abandons ('backtracks') a partial candidate the moment it cannot possibly lead to a valid solution.
It's a depth-first walk of an implicit decision tree: each node is a partial state, each edge a choice, each leaf a complete candidate.
Why it matters
It's the canonical way to enumerate ALL solutions (every subset, every permutation, every board arrangement) or to find one under constraints, when no closed-form or greedy shortcut exists.
Interviewers use it to test whether you can manage recursive state cleanly — the choose/explore/un-choose discipline — and whether you prune, which is the difference between 'times out' and 'passes'.
How it works
The universal template: if the state is a complete solution, record it; otherwise, for each valid next choice — make the choice, recurse, then UNDO it before trying the next.
The undo step is the heart of the technique: it restores state so sibling branches start clean. Forget it and every branch inherits the last branch's garbage.
Pruning cuts branches early: skip choices that already violate constraints (a queen attacked, a sum exceeded), collapsing an exponential tree to something tractable.
Where it's used
Constraint solvers, Sudoku and puzzle engines, regex backtracking matchers, dependency resolution, and automated theorem provers all backtrack.
Analogy: Exploring a maze with a ball of string: at each junction you pick a corridor and mark your path; hit a dead end and you reel the string back to the last junction to try the next corridor. The string IS the undo.
Interactive diagram
Each element is a binary choice — include (left) or skip (right). The tree has 2³ = 8 leaves.
All subsets of [1, 2, 3]
At each element the recursion makes a binary choice: include it or skip it. The decision tree below grows one level per element — 2ⁿ leaves in total.
1 / 24
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
The choose/explore/un-choose template
One skeleton behind every backtracking problem.
25 min
Subsets: the include/exclude tree
Binary decisions; 2ⁿ leaves; the simplest decision tree.
20 min
Permutations
Used-set or swap-in-place; n! leaves; duplicate handling.
25 min
Combinations & combination sum
Start-index to avoid re-picking; reuse vs no-reuse.
25 min
Pruning and constraint checks
Cutting dead branches early — the feasibility multiplier.
25 min
N-Queens
Column/diagonal sets; place row by row; the classic prune.
30 min
Word search & grid backtracking
Mark-visited-then-restore on a 2-D board.
25 min
Complexity of backtracking
Branching factor ^ depth; why pruning matters more than Big O.
15 min
Operations
Subsets (include / exclude)
At each element, branch two ways. Every root-to-leaf path is one subset; the recursion IS the tree.
All subsets of [1, 2, 3]
At each element the recursion makes a binary choice: include it or skip it. The decision tree below grows one level per element — 2ⁿ leaves in total.
1 / 24
1defsubsets(nums:list[int])->list[list[int]]:2"""All 2^n subsets. O(n · 2^n) time (each subset copied)."""3result:list[list[int]]=[]4path:list[int]=[]56defbacktrack(start:int)->None:7result.append(path[:])# every node is a valid subset8foriinrange(start,len(nums)):9path.append(nums[i])# choose10backtrack(i+1)# explore (i+1: no reuse, no dupes)11path.pop()# un-choose1213backtrack(0)14returnresult
Duplicates: sort, and skip i if nums[i]==nums[i-1] and not used[i-1] (skip when the equal PRIOR is unused).
Single element → one permutation.
Swap-based variants avoid the used array but scramble order.
Common mistakes
Forgetting to reset used[i] = False on the way out — later branches think the element is taken.
Using start-index logic (that generates COMBINATIONS, not permutations).
N-Queens (constraint pruning)
Place one queen per row; before placing, check column and both diagonals via sets. Invalid placements are pruned instantly.
N-Queens (constraint pruning)
1defsolve_n_queens(n:int)->int:2"""Count valid N-Queens placements. Pruned backtracking."""3cols:set[int]=set()4diag:set[int]=set()# row - col (↘ diagonals)5anti:set[int]=set()# row + col (↙ diagonals)6count=078defbacktrack(row:int)->None:9nonlocalcount10ifrow==n:# all rows placed11count+=112return13forcolinrange(n):14ifcolincolsor(row-col)indiagor(row+col)inanti:15continue# prune: this square is attacked16cols.add(col);diag.add(row-col);anti.add(row+col)17backtrack(row+1)18cols.remove(col);diag.remove(row-col);anti.remove(row+col)1920backtrack(0)21returncount
Time: O(n!) worst, far less with pruningSpace: O(n)
Edge cases
row − col identifies ↘ diagonals; row + col identifies ↙ — both constant along a diagonal.
n = 1 → 1 solution; n = 2, 3 → 0.
Placing per row already prevents two queens sharing a row — no check needed for that.
Common mistakes
Checking attacks by scanning the board (O(n) per square) instead of O(1) set membership.
Removing from the wrong set on backtrack, corrupting the constraint state.
Complexity analysis
Operation
Best
Average
Worst
Space
Subsets
O(2ⁿ)
O(n·2ⁿ)
O(n·2ⁿ)
O(n)
Permutations
O(n!)
O(n·n!)
O(n·n!)
O(n)
Combinations (n choose k)
O(C(n,k))
O(k·C(n,k))
O(k·C(n,k))
O(k)
N-Queens
—
≪ O(n!) with pruning
O(n!)
O(n)
Sudoku / grid search
—
exponential, pruning-dependent
exponential
O(cells)
Backtracking is exponential by nature — its Big O counts leaves. Pruning changes the CONSTANT and the practical runtime dramatically without changing the worst-case class.
Python implementation
Production-quality code with type hints, validation, and docstrings.
Word Search: backtracking on a grid with restore
1defword_search(board:list[list[str]],word:str)->bool:2"""Doeswordexistasapathofadjacentcells(noreuse)?3O(rows·cols·4^len(word))worstcase."""4ifnotboardornotboard[0]:5returnFalse6rows,cols=len(board),len(board[0])78defbacktrack(r:int,c:int,i:int)->bool:9ifi==len(word):10returnTrue# matched the whole word11ifnot(0<=r<rowsand0<=c<cols)orboard[r][c]!=word[i]:12returnFalse# prune: off-grid or mismatch1314board[r][c]="#"# mark visited (choose)15found=(16backtrack(r+1,c,i+1)17orbacktrack(r-1,c,i+1)18orbacktrack(r,c+1,i+1)
What interviewers expect you to know
The template you must internalise
if solution complete → record and return; else for each valid choice: choose → recurse → un-choose.
Subsets/combinations use a START INDEX (order fixed, no reuse). Permutations use a USED SET (all positions open).
The un-choose (pop / unmark / remove from set) restores state for siblings — the single most important line.
Pruning is the real skill
Check feasibility BEFORE recursing, not at the leaf — an early `if invalid: continue` prunes whole subtrees.
Sort first to enable 'skip duplicates at this level' and 'break when the remaining minimum already overshoots' (combination sum).
State pruning cheaply: N-Queens uses three sets for O(1) attack checks instead of scanning the board.
Classic follow-ups
"Handle duplicate inputs without duplicate outputs" — sort, then skip nums[i]==nums[i-1] at the same tree level.
"Count solutions vs list them" — counting needs no path copies (cheaper); listing needs path[:] at each leaf.
"Why is this exponential and is that OK?" — the OUTPUT is exponential (2ⁿ subsets), so you can't beat it; pruning fights the constant.
Common mistakes
Missing the un-choose
Every choose must have a matching undo (pop/unmark/remove). Without it, sibling branches inherit corrupted state — the number-one backtracking bug.
Appending the mutable path
result.append(path) stores a reference; when path empties on the way up, every stored 'solution' becomes []. Always append path[:] (a copy).
Start-index vs used-set mixup
Start-index generates combinations/subsets; a used-set generates permutations. Using the wrong one silently solves a different problem.
Pruning at the leaf, not the branch
Checking validity only when the candidate is complete explores the whole tree. Prune the moment a partial state is doomed.
Duplicate outputs from duplicate inputs
Unsorted input with equal elements yields repeated results. Sort, then skip equal siblings at each level.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
O(1) effectively - at most 3^3 = 27 dot placements bounded by fixed lengths, each O(1) to validate time · O(1) recursion depth (at most 4) plus output space
HardConstrained cell filling with backtracking~40 min
Commonly associated with: Amazon, Microsoft, Uber
O(9^m) worst case where m is the number of empty cells, pruned heavily by the three constraint sets time · O(m) recursion depth plus O(1) fixed-size constraint sets space
HardRow-by-row placement with diagonal conflict sets~40 min
Commonly associated with: Amazon, Google, Apple
O(n!) in the worst case, since each row has fewer valid columns as queens accumulate time · O(n) for the three sets and recursion, plus O(n^2) per stored board space
Topic quiz
5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
How is backtracking different from plain DFS?
Backtracking IS DFS on an implicit decision tree, plus the explicit undo of state between choices and pruning of doomed branches. Graph DFS marks nodes visited permanently; backtracking un-marks them so other paths can reuse the state.
When does a backtracking problem become a DP problem?
When distinct branches revisit the SAME subproblem (overlapping subproblems), you can memoize the results — converting exponential backtracking into polynomial DP. If every path leads to a unique state (pure enumeration), DP doesn't help.
How do I handle duplicates cleanly?
Sort the input first. Then within each recursion level, skip an element equal to its predecessor (with the right 'used' guard for permutations). Sorting turns duplicate-skipping into a simple adjacency check.