Backtracking —
Choose, explore, undo, try the next one.
Backtracking explores every possible choice by making one, recursing to explore what follows, then undoing that choice before trying the next — the "undo" step is what separates it from plain recursion. Watch a choice get made and then explicitly reversed on LearnBug while generating all permutations of a small list.
What is Backtracking?
A pattern for exploring every possible combination of choices: at each step, pick an option, recurse to see what happens next, and then undo that pick before returning — so the next option can be tried from a clean state. It's how you generate permutations, subsets, and solve constraint puzzles like N-Queens or Sudoku.
Why visualization helps
The "undo" line (path.pop()) is easy to skim past in code but is the entire mechanism that makes backtracking work — without it, choices would leak between branches that should be independent. LearnBug shows the current partial path growing and shrinking live, so you watch a choice get made and then explicitly reversed.
The pattern behind every backtracking problem
Choose — add an option to the current path
path.append(num) — commit to trying this value next, and record it so the recursive call below can see the full path so far.
Explore — recurse to see what follows
Call the function again with the updated path — either it finds a complete solution (path length equals input length) or it keeps choosing.
Un-choose — undo before trying the next option
path.pop() — this is the actual "backtrack." It resets the path back to how it was before this choice, so the next option starts clean.
Generate permutations of [1, 2, 3] — a partial trace
Choose 1: path = [1] — recurse to explore what follows
1 isn't in the path yet, so it's a valid choice. It gets appended, and the function calls itself to continue building from here.
Choose 2, then 3: path = [1, 2, 3] — a complete permutation, save it
Both 2 and 3 get chosen the same way, one recursive call deeper each time. When the path length matches the input length, this is a full permutation — it gets copied into the results.
Backtrack: pop 3, pop 2 — path returns to [1], now try 3 before 2
This is the "undo" in action. After saving [1,2,3], the recursion returns, and BEFORE trying the next option, the path is popped back to [1] — otherwise 3 and 2 would still be "stuck" in the path.
This continues for every starting choice — eventually all 6 permutations are found
The same choose/explore/un-choose pattern repeats: starting with 1 gives [1,2,3] and [1,3,2]; starting with 2 gives [2,1,3] and [2,3,1]; starting with 3 gives [3,1,2] and [3,2,1].
Return: 6 permutations ✓ 3! = 6, every one reached by choosing, exploring, and undoing
Backtracking permutations
def permute(nums, path, result):
if len(path) == len(nums):
result.append(path[:]) # complete permutation — copy it, don't reference it
return
for num in nums:
if num in path:
continue # skip values already used in this path
path.append(num) # CHOOSE
permute(nums, path, result) # EXPLORE
path.pop() # UN-CHOOSE — backtrack
result = []
permute([1, 2, 3], [], result)
print(result)Complexity Notes
Frequently asked questions
What actually distinguishes backtracking from plain recursion?
The explicit "undo" step. Plain recursion (like factorial) never needs to reverse a decision — each call's work is independent. Backtracking shares mutable state (the path) across all branches, so each branch must clean up its own choice before control returns to try a sibling choice, or that shared state would leak between branches.
Why does result.append(path[:]) use a slice copy instead of just path?
path is the same list object throughout the entire recursion — it's mutated in place as choices are made and undone. If you appended path directly, every entry in result would be a reference to that same list, and by the time recursion finishes, they'd all show whatever path last happened to contain (usually empty). path[:] creates an independent snapshot.
What is "pruning" and why does it matter?
Pruning means checking a constraint before recursing further, so an obviously-invalid branch is abandoned immediately instead of being explored to completion first. In N-Queens, for example, checking "does this queen attack a previously placed one?" before recursing avoids exploring an entire doomed subtree — the difference between a fast solution and one that times out.
What other problems use this exact same pattern?
Subsets (choose whether to include each element or not), combinations, N-Queens, Sudoku solving, word search in a grid, and generating valid parentheses combinations all follow the same choose/explore/un-choose shape — only what counts as a "choice" and a "valid state" changes.
Watch a choice get made — and explicitly undone
Paste your backtracking solution into LearnBug and see the path grow and shrink live.