aloalgo.comIntroduction to Backtracking
Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking") as soon as you determine a path won't lead to a valid solution.The Core Idea
Backtracking follows a simple pattern:- Choose – Make a choice at the current step
- Explore – Recurse to explore what follows
- Unchoose – Undo the choice and try another option
The Template
Example: Generate All Subsets
The simplest backtracking problem: generate all possible subsets of a list. For each element, we choose to either include it or not.Example: Generate Permutations
Generate all orderings of a list. Unlike subsets, order matters and we use all elements.Example: Combination Sum
Find all combinations that sum to a target. This adds a constraint: we prune paths that exceed the target.When to Use Backtracking
- "Generate all..." – All permutations, subsets, combinations
- Constraint satisfaction – Sudoku, N-Queens
- Path finding with constraints – Word search, mazes
- Combinatorial search – Find combinations that meet criteria
Common Interview Tips
- Start with the template: Choose, explore, unchoose. Every backtracking problem follows this pattern.
- Identify your choices: What decisions do you make at each step?
- Define when to stop: What makes a valid solution?
- Prune early: The earlier you detect invalid paths, the more efficient your solution.
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.