Backtracking — How the Pattern Works
Backtracking is a systematic depth-first search paradigm that constructs candidate solutions incrementally through a sequence of choices, abandoning any partial state the moment it violates problem constraints. At every recursive step, it maintains a single shared mutable state (such as a partial list, board, or visited marker) under the choose-explore-undo invariant: mutate the state before recursing and restore it immediately upon return so sibling branches observe an untouched prefix. By pruning invalid or suboptimal branches at internal nodes of the decision tree rather than generating and validating complete configurations at the leaves, backtracking slashes combinatorial search spaces (e.g., O(C(n^2, n)) to O(n!) in N-Queens, or O(2^n) to O(n^3) when initial choices force the remainder) while keeping auxiliary state space proportional to the recursion depth O(d).
- Prompts asking to enumerate all valid configurations, paths, subsets, combinations, or string partitions rather than returning a single greedy value.
- Constraint-satisfaction puzzles on 2D grids or boards (N-Queens, Sudoku, Word Search, Unique Paths III) where placing an item or visiting a cell restricts subsequent choices and can hit dead ends.
- Small input bounds (n <= 15 to 20, grid size <= 9 x 9, or k <= 10) signaling an exponential or factorial decision tree paired with aggressive constraint or branch-and-bound pruning.
- Optimization problems lacking greedy-choice or polynomial-state DP structure (such as equal-sum bin packing in Matchsticks to Square or debt settlement in Optimal Account Balancing) where early assignments constrain future feasibility.
- Tree or DAG path-enumeration tasks where routes share common prefixes and a single mutable path list can be grown on descent and popped on return.
- Appending the live mutable path reference (result.append(path)) instead of a snapshot copy (result.append(list(path)) or "".join(path)), leaving every recorded entry empty once backtracking unwinds.
- Forgetting to undo in-place state mutations (restoring board[r][c], removing keys from conflict sets, or reverting bucket sums) before returning, which corrupts state for subsequent sibling branches.
- Using a global visited set across the entire search when enumerating all paths in a graph or grid, which permanently blocks shared downstream nodes after the first path visits them instead of only blocking cycles along the active path.
- Validating rules only at leaf nodes or omitting symmetry-breaking invariants (passing i + 1 for combinations, sorting items descending in bin packing, or skipping adjacent duplicate deletions), resulting in redundant O(n!) exploration.
def backtrack_combinations(candidates, k):
result, path = [], []
def dfs(start):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(candidates)):
if is_valid(candidates[i], path):
path.append(candidates[i])
dfs(i + 1)
path.pop()
dfs(0)
return resultdef grid_backtrack(grid, r, c, idx, target):
if idx == len(target):
return True
if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] != target[idx]:
return False
saved, grid[r][c] = grid[r][c], "#"
found = any(grid_backtrack(grid, r + dr, c + dc, idx + 1, target)
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)))
grid[r][c] = saved
return founddef count_placements(n):
cols, diag, anti = set(), set(), set()
def dfs(r):
if r == n:
return 1
ways = 0
for c in range(n):
if c not in cols and r - c not in diag and r + c not in anti:
cols.add(c); diag.add(r - c); anti.add(r + c)
ways += dfs(r + 1)
cols.remove(c); diag.remove(r - c); anti.remove(r + c)
return ways
return dfs(0)def branch_and_bound(items):
best = float("inf")
def dfs(i, cost):
nonlocal best
if cost >= best or i == len(items):
best = min(best, cost) if i == len(items) else best
return
for choice, delta in valid_choices(items[i]):
apply_choice(choice)
dfs(i + 1, cost + delta)
undo_choice(choice)
dfs(0, 0)
return best