Backtracking Pattern
Backtracking builds candidates incrementally and abandons a path as soon as it can't lead to a valid solution. It's the go-to for generating combinations, permutations, and constraint-satisfaction answers.
Typical complexity: Exponential in the worst case; pruning is what makes it tractable
When to use it
- You must enumerate all subsets, permutations, or arrangements.
- The problem has constraints you can check partway to prune.
- A greedy or DP formulation doesn't capture the branching choices.
Practice problems
Read the approach or generate an interactive, step-by-step lesson:
Deep dive
Backtracking Pattern: How to Generate Combinations Without Losing Your Mind
Learn the recursive choose-explore-unchoose pattern behind subsets, permutations, combinations, and many classic search problems.
Master backtracking by doing
codebrew.ai turns each problem into an interactive lesson — trace the algorithm variable by variable until the pattern clicks.
Start a free lesson