Backtracking
Explore all possibilities with systematic trial and error.
8
Problems
0
Easy
0
Medium
8
Hard
How Backtracking Works
Backtracking systematically explores all possible solutions by building candidates incrementally and abandoning ("pruning") paths that can't lead to valid solutions. It follows a choose-explore-unchoose pattern: at each step, make a choice, recurse to explore further, then undo the choice to try alternatives. The key optimization is pruning — recognizing early when a partial solution can't possibly work, saving time by not exploring that entire subtree.
When to Use Backtracking
Pattern Recognition
Look for these trigger words in problem statements:
subsets
backtracking
combination sum
permutations
subsets ii
combination sum ii
word search
palindrome partitioning
n-queens
Common Mistakes
- Forgetting to unchoose (backtrack) after exploring — this corrupts the state for sibling branches
- Not pruning effectively, leading to exponential blowup on large inputs
- Creating new copies of the state at every level instead of modifying in place (wastes memory)
- Generating duplicate solutions — use sorting and skip duplicates at each level
When NOT to Use Backtracking
- When an optimal substructure exists (use dynamic programming instead)
- When a greedy approach gives the optimal solution
- When the search space is too large even with pruning (consider approximation algorithms)
Practice Problems
Compare With Other Patterns
Master Backtracking
Build pattern recognition with interactive MCQs. Understand why to use Backtracking, not just how.
Download LeetEye Free