Backtracking Algorithms
Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point in time.
1. The Core Concept
Think of backtracking as exploring a maze. You choose a path and follow it until you hit a dead end. Once you hit a dead end, you turn back ("backtrack") to the last junction and try a different path.
- Depth-First Search (DFS): Backtracking uses DFS to explore the "state space tree".
- Pruning: If the current partial solution cannot possibly lead to a valid full solution, we abandon it immediately. This avoids wasting time on invalid paths.
2. General Structure
Most backtracking algorithms follow this template:
def backtrack(candidate):
# 1. Check if we found a valid solution
if is_solution(candidate):
output(candidate)
return
# 2. Iterate through all possible next steps
for next_step in possible_steps:
if is_valid(next_step):
# 3. Make a choice (Place)
place(next_step)
# 4. Recurse (Explore)
backtrack(next_step)
# 5. Undo the choice (Backtrack)
remove(next_step)3. Example: Permutations
Given an array [1, 2, 3], return all possible permutations.
def permute(nums):
result = []
def backtrack(path):
# Base Case: If path length equals input length, we have a permutation
if len(path) == len(nums):
result.append(path[:]) # Append a copy of the path
return
for num in nums:
# Constraint: Don't use the same number twice
if num in path:
continue
path.append(num) # Choose
backtrack(path) # Explore
path.pop() # Un-choose (Backtrack)
backtrack([])
return result4. Common Use Cases
Backtracking is ideal for Constraint Satisfaction Problems:
- Puzzles: Sudoku, Crosswords, N-Queens problem.
- Combinatorics: Generating permutations, combinations, or subsets.
- Pathfinding: Finding a path through a maze.
5. Backtracking vs. Dynamic Programming
- Backtracking: Explores all potential solutions (brute force with pruning). It is typically used when you need all solutions or when the problem doesn't have optimal substructure.
- Dynamic Programming: Breaks problems into overlapping subproblems and caches results. It is typically used for optimization problems (finding the best solution).
programming/algorithms programming/dynamic-programming programming/functions-and-scope