Introduction
Backtracking is a general algorithmic technique for solving problems by incrementally building candidates to a solution and abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot possibly lead to a valid solution. It is essentially a refined brute-force search that explores the state space as a tree, pruning branches that violate constraints early instead of exploring them fully. Classic applications include N-Queens, Sudoku, generating permutations/combinations, and constraint satisfaction problems.
Cricket analogy: Setting a batting order by trying a sequence, and pulling a batter back out the moment the combination clearly can't chase the target, is backtracking: it's brute force with early pruning instead of playing out every full XI arrangement.
Approach/Syntax
def backtrack(state, choices):
if is_solution(state):
record_solution(state)
return
for choice in choices(state):
if is_valid(state, choice):
state.append(choice) # choose
backtrack(state, choices) # explore
state.pop() # un-choose (backtrack)
Explanation
Every backtracking algorithm follows the same three-step rhythm at each recursive call: choose an option, explore deeper by recursing with that option applied, then unchoose it to restore the previous state before trying the next option. The 'unchoose' step is what distinguishes backtracking from plain recursive enumeration -- it lets a single mutable state object (a partial board, path, or set) be reused across the entire search instead of copying it at every level, which keeps memory usage proportional to the depth of the search tree rather than its size. A validity check (is_valid) applied before recursing is the pruning mechanism: it stops the algorithm from wasting time exploring subtrees that are already known to violate a constraint.
Cricket analogy: Each bowling-change decision follows choose-explore-unchoose: bring on a spinner, bowl the over and see the result, then if it goes for 20 runs, pull them back and restore the previous field setting before trying a pacer instead.
Example
def subsets(nums):
"""Generate all subsets of nums using choose/explore/un-choose."""
result = []
current = []
def backtrack(start):
# Every prefix 'current' is itself a valid subset.
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i]) # choose
backtrack(i + 1) # explore
current.pop() # un-choose
backtrack(0)
return result
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Complexity
Backtracking algorithms rarely have a simple closed-form time complexity because their whole purpose is to prune the search tree, but the worst case is bounded by the size of the full state space -- for subset generation this is O(2^n) since each element is either included or excluded, and O(n) auxiliary space is used for the recursion stack and the current partial solution (excluding the output itself). In problems with strong constraints, such as N-Queens or Sudoku, pruning reduces the number of nodes actually visited far below the theoretical worst case, which is why backtracking is practical even though its worst-case bound looks exponential.
Cricket analogy: Trying every possible batting order for 11 players without any constraints would be a factorial explosion, but strict constraints like 'openers must bat first' prune most combinations away, so a real net session tests far fewer orders than the theoretical worst case.
Key Takeaways
- Backtracking explores a state-space tree via choose, explore, un-choose (backtrack).
- Pruning with a validity check before recursing avoids wasted work on doomed branches.
- State is mutated and restored in place, keeping space complexity proportional to recursion depth.
- Worst-case time is exponential (bounded by the full search space), but pruning makes it practical.
- Backtracking underlies N-Queens, Sudoku, permutation/combination generation, and many constraint problems.
Practice what you learned
1. What is the defining characteristic of the backtracking paradigm?
2. In the choose/explore/un-choose pattern, what is the purpose of the 'un-choose' step?
3. Why does pruning matter in backtracking algorithms?
4. What is the typical worst-case time complexity class of backtracking algorithms that explore all subsets of n items?
Was this page helpful?
You May Also Like
N-Queens Problem
Place N queens on an N×N chessboard so none attack each other, using backtracking with column, diagonal pruning.
Sudoku Solver
Fill a 9x9 Sudoku grid using backtracking with row, column, and box constraint checks.
Generating Permutations and Combinations
Use backtracking to enumerate all permutations and combinations of a collection systematically.
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.