The core idea: choose, explore, undo
Imagine walking a maze while unspooling a thread. At each junction you pick a direction and keep going. When you hit a wall, you follow the thread back to the last junction and try a different direction. Backtracking is that thread-and-junction idea turned into code: make a choice, recurse to explore its consequences, and if that path fails, undo the choice and try the next one.
What makes it more than blind trial and error is that you abandon a path the instant it is provably hopeless, not only when it is fully complete. If placing a queen already puts two queens on the same diagonal, there is no point filling the rest of the board, so you undo and move on. That early abandonment is the whole point.
How it works: the state-space tree and pruning
Formally, backtracking performs a depth-first search over a state-space tree. Each node is a partial solution and each edge is one additional choice: the next number in a permutation, the next queen's column, the next digit in a Sudoku cell. A recursive function tries every valid choice at the current level, and after each recursive call it restores state so the next choice starts clean. When the partial solution is complete you record it; when no choice is valid the call simply returns and control flows back up the tree.
Two moves define every backtracking function: the constraint check (is this choice still valid?) and the undo (remove the choice before trying the next). The constraint check is where pruning happens, and the tighter and earlier it is, the more of the tree you skip. This is exactly the kind of process that clicks once you watch it animate: you can see the recursion dive down a branch, hit a violated constraint, and retreat one level to try the next option.
One template, many problems
Almost every backtracking solution fits the same shape: a base case that records a completed solution, a loop over candidate choices, and a choose / recurse / undo trio inside that loop. Learn that skeleton once and permutations, subsets, combination sum, N-Queens, word search, and Sudoku all become variations on where you get the candidates and how you check validity.
The differences are mostly in candidate generation. For subsets you decide include-or-skip on each element; for permutations you pick any unused element; for grid problems you branch into neighboring cells. The recursion, the base case, and the undo stay recognizably the same.
def permutations(nums):
result = []
def backtrack(path, remaining):
if not remaining: # complete solution
result.append(path[:]) # store a COPY, not the shared list
return
for i in range(len(remaining)):
path.append(remaining[i]) # choose
backtrack(path, remaining[:i] + remaining[i + 1:]) # explore
path.pop() # undo
backtrack([], nums)
return resultBacktracking's cost is the number of nodes it visits in the state-space tree, so it is problem-dependent: subsets are O(2^n), N-Queens is roughly O(n!). Strong pruning (constraint checks that fail early) massively cuts the real work but does not change the Big-O worst case.
When to use it
- Enumerating all permutations, combinations, or subsets of a set
- Constraint-satisfaction puzzles like N-Queens, Sudoku, or crossword filling
- Grid search where you explore a path and then retreat, such as word search
- Partitioning and combination-sum style problems that need every valid arrangement
Watch out for
- Forgetting to undo the choice (not popping or restoring state), so state leaks between branches and results become wrong
- Storing a reference to the mutable path instead of a copy, so every recorded result points to the same list that ends up empty
- Weak or missing pruning and no visited/index guard, which explores the full tree, revisits states, and times out on larger inputs
Backtracking is one of the most common medium-difficulty interview categories — expect problems like Permutations, Subsets, Combination Sum, Generate Parentheses, Word Search, N-Queens, and Sudoku Solver. Interviewers care less about a clever trick and more about whether you can recognize the pattern, sketch the decision tree, and write a clean recursive function with a correct base case and a matching undo step. Strong signals include stating the state-space size up front, pruning invalid branches early, and appending a copy of the current path rather than a shared reference. Being able to explain why the time complexity is exponential, and where pruning actually helps in practice, is what sets a confident answer apart.