Tree & GraphIntermediate
Backtracking
Build solutions incrementally, abandoning a path as soon as it cannot lead to a valid solution.
Problem: Subsets of [1, 2, 3]
Generate all subsets by making include/exclude decisions for each element
Start: exploring all possibilities
Exploring
Valid
Pruned
Solution
Step 1/9
Speed:
When to Use
- Generate all permutations/combinations
- Constraint satisfaction (Sudoku, N-Queens)
- All possible paths
- Subset generation
Key Indicators
- "All", "every", "generate" combinations/permutations
- Constraint satisfaction
- Try and undo
- Decision tree exploration
Complexity
Time
O(2^n) or O(n!)
Space
O(n) recursion depth
Common Problems
PermutationsSubsetsN-QueensSudoku SolverCombination SumWord Search
Code
def backtrack(path, choices):
if is_solution(path):
results.append(path[:])
return
for choice in choices:
if is_valid(choice):
path.append(choice)
backtrack(path, remaining_choices)
path.pop() # undoWant all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)