"Backtracking is how you brute-force intelligently: make a choice, explore where it leads, and the instant it hits a wall, undo it and try the next. It's a maze-runner that remembers to walk back out of dead ends."
DFS Through the Space of Choices
Many problems ask you to build a solution by making a sequence of choices: which number goes next in this permutation, which queen goes in this column, which digit fills this Sudoku cell. Backtracking explores that space of partial solutions depth-first (it's DFS, from the Graphs track, over an implicit decision tree). The template is three beats: choose an option, recurse to explore the consequences, then un-choose (undo the choice) so you can try the next option. That 'undo' is the backtrack — it's what lets one piece of code explore every branch without the branches contaminating each other.
The choose / explore / un-choose Template
Almost every backtracking solution has the same skeleton: if the current partial solution is complete, record it; otherwise, loop over the available choices, and for each — apply it, recurse, then revert it. The revert step is the one beginners forget, and forgetting it means earlier choices leak into later branches. Get the choose/recurse/un-choose rhythm into your fingers and a whole genre of problems opens up: permutations, subsets, combinations, N-queens, Sudoku, maze-solving, word search, generating valid parentheses.
Backtracking is DFS over a tree of choices: choose an option, recurse to explore, then UN-choose to try the next. The undo is the backtrack. The exhaustive search space is exponential — pruning (abandoning doomed branches early) is what makes it tractable.
Pruning: the Difference Between Tractable and Hopeless
The decision space is usually exponential — there are n! permutations, 2ⁿ subsets — so naive exhaustive search is hopeless at scale. The thing that rescues backtracking is pruning: abandoning a branch the moment it's provably doomed, before exploring it fully. In N-queens, if placing a queen already creates a conflict, you don't recurse into that branch at all — you cut the entire subtree below it. Good pruning can shrink an astronomically large search to something that finishes in milliseconds. The art of backtracking isn't the choose/un-choose mechanics (those are rote); it's finding the earliest possible moment to say 'this branch can't work' and cutting it.
Pippa's Confession
My first permutation generator returned garbage — each result had leftovers from the previous one. Dad spotted it instantly: I'd done choose and recurse but forgotten to un-choose. The path I was building never got cleaned up between branches. Adding the one undo line fixed everything. And the deeper lesson came with N-queens: my correct-but-slow version checked conflicts at the end; pruning them during placement turned a timeout into an instant answer. Backtracking taught me that when you detect failure matters as much as that you detect it.
Code
Permutations: choose, explore, un-choose·python
# All permutations via backtracking: choose / recurse / un-choose.
def permutations(items):
result = []
path = []
used = [False] * len(items)
def backtrack():
if len(path) == len(items): # complete solution -> record it
result.append(path[:]) # copy! path keeps changing
return
for i in range(len(items)):
if used[i]:
continue # prune: can't reuse an element
path.append(items[i]); used[i] = True # CHOOSE
backtrack() # EXPLORE
path.pop(); used[i] = False # UN-CHOOSE (the backtrack!)
backtrack()
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
# The path.pop() + used[i]=False is the UNDO. Forget it and earlier choices
# leak into later branches -> wrong answers. N-queens adds PRUNING: skip any
# placement that conflicts, cutting whole subtrees before exploring them.
Adapt the template to generate all SUBSETS of [1,2,3] (the power set, 2³ = 8 of them). At each element you make a binary choice: include it or skip it. Sketch the choose/recurse/un-choose structure. Then explain, for N-queens, what 'pruning' means and why checking conflicts DURING placement beats checking only at the end.
Hint
For subsets: at index i, choose to include items[i] (append, recurse, pop) then choose to skip it (just recurse) — 8 leaves. N-queens pruning: the moment a queen conflicts with an existing one, skip that placement and don't recurse — you cut the entire subtree of arrangements below it, instead of building full boards and rejecting them at the end.
Progress
Progress is local-only — sign in to sync across devices.