Backtracking Template: Choose, Explore, Unchoose
Implement the three-step backtracking skeleton, trace it on a small example, and identify where pruning conditions slot in.
What is Backtracking?
Backtracking is a systematic method for finding all (or some) solutions by exploring every candidate incrementally and abandoning (pruning) a branch as soon as it is determined that the branch cannot yield a valid solution. It is the algorithm behind solving Sudoku, generating permutations, and finding all valid combinations. Think of it as a depth-first search on a decision tree.
# Mental model: backtracking explores a decision tree
# At each node you make a choice, go deeper, then undo it
#
# Tree for generating subsets of [1,2,3]:
# []
# / \
# [1] []
# / \ / \
# [1,2][1][2] []
# ...
# Every leaf is a potential solution
# Pruning cuts branches early based on constraints
print('Backtracking = DFS on decision tree with pruning')The Three-Step Template
Every backtracking function follows three steps: Choose — pick the next candidate from available options. Explore — recurse with that choice, moving one level deeper in the decision tree. Unchoose — undo the choice after returning from recursion to restore state for the next candidate. This pattern is also called add/recurse/remove or mark/recurse/unmark in different contexts.
def backtrack(current_state, choices, results):
# Base case: is current_state a complete solution?
if is_complete(current_state):
results.append(list(current_state)) # record solution
return
for choice in choices:
if is_valid(choice, current_state): # pruning condition
# 1. CHOOSE
current_state.append(choice)
# 2. EXPLORE
backtrack(current_state, choices, results)
# 3. UNCHOOSE (backtrack)
current_state.pop()
# Placeholder functions — filled per problem
def is_complete(state): return True
def is_valid(choice, state): return TrueAll lessons in this course
- Backtracking Template: Choose, Explore, Unchoose
- Subsets and Power Set
- Permutations and Combinations
- N-Queens and Constraint Propagation