Topic 8 of 20
Recursion & Backtracking
Think recursively, then explore every choice and undo it: subsets, permutations and search.
The concept
Recursion solves a problem by solving smaller copies of the same problem. Every recursive function needs a base case that stops, and a recursive step that makes progress toward it. The fastest way to get comfortable is to trust the function: assume the recursive call correctly solves the smaller problem, and only reason about how to combine its answer.
Backtracking is recursion that explores a tree of choices. At each step you choose an option, recurse, then undo the choice before trying the next one. Almost every subsets, permutations and combinations question fits a single template: choose → explore → un-choose. Duplicates are handled by sorting and skipping equal neighbours at the same depth.
The difference between an accepted and a timed-out backtracking solution is pruning: stop exploring as soon as a partial solution cannot succeed. This topic comes before trees and graphs on purpose, because DFS is just recursion over a structure, and dynamic programming is recursion plus memory.
Patterns you will learn
Problems, in order
- 1Fibonacci NumberEasy
The standard first recursion; also motivates memoisation later.
Recursion BasicsReported at: AmazonAppleMicrosoft+5 - 2Power of TwoEasy
A simple base case and reduction, with a bit-trick alternative.
Recursion BasicsReported at: AmazonAppleGoogle+1 - 3Binary WatchEasy
Enumerating combinations of bits; a light warm-up for combinatorial search.
EnumerationReported at: Google - 4Pow(x, n)Medium
Fast exponentiation by halving; O(log n) recursion.
Divide & ConquerReported at: MetaAmazonGoogle+5 - 5K-th Symbol in GrammarMedium
Solving by relating a node to its parent, not by building the string.
Recursion on StructureReported at: Adobe - 6SubsetsMedium
The base template for backtracking and bitmask enumeration.
Subsets (Include / Exclude)Reported at: MetaAmazonGoogle+6 - 7Subsets IIMedium
Sort and skip equal siblings to avoid duplicates.
Subsets + Duplicate SkippingReported at: MetaAmazonBloomberg+1 - 8PermutationsMedium
Swap-based or used-array permutation generation.
PermutationsReported at: AmazonMetaGoogle+6 - 9Permutations IIMedium
Duplicate handling in permutations.
Permutations + Duplicate SkippingReported at: AmazonMicrosoft - 10
- 11Combination SumMedium
Reuse allowed; a pruned backtracking classic.
Combinations (Unbounded Reuse)Reported at: AmazonMetaMicrosoft+6 - 12Combination Sum IIMedium
Each element used once, with duplicate skipping.
Combinations + Duplicate SkippingReported at: AmazonMetaBloomberg+1 - 13
- 14
Cartesian-product backtracking; a frequent phone-screen problem.
Cartesian ProductReported at: AmazonMicrosoftMeta+5 - 15Generate ParenthesesMedium
Generating only valid states instead of filtering them.
Constrained GenerationReported at: MetaAmazonMicrosoft+8 - 16Letter Case PermutationMedium
Binary choice per character.
Subsets (Include / Exclude)Reported at: Microsoft - 17Palindrome PartitioningMedium
Partition a string with a validity check at each cut.
PartitioningReported at: GoogleAppleAmazon+2 - 18Restore IP AddressesMedium
Partitioning with strict segment rules.
Partitioning with ConstraintsReported at: AmazonMicrosoftMeta+1 - 19Word SearchMedium
DFS on a grid with visited marking and undo.
Grid BacktrackingReported at: AmazonMicrosoftMeta+4 - 20
Shows how sorting and pruning make exponential search feasible.
Constraint Search with PruningReported at: GoogleAmazonLinkedIn - 21N-QueensHard
The canonical constraint-satisfaction problem.
Constraint Search with PruningReported at: AmazonMetaMicrosoft+4 - 22N-Queens IIHard
Counting instead of listing; sets or bitmasks for speed.
Constraint Search with PruningReported at: ByteDance / TikTok - 23Sudoku SolverHard
Full constraint propagation by backtracking.
Constraint Search with PruningReported at: AmazonAppleGoogle+8 - 24
Carries running totals and handles multiplication precedence.
Backtracking with StateReported at: Meta - 25
Minimum removals with deduplication; asked at Meta.
BFS / Backtracking with PruningReported at: MetaAmazon