Skip to content

Topic 8 of 20

Recursion & Backtracking

Think recursively, then explore every choice and undo it: subsets, permutations and search.

25 problems3 Easy17 Medium5 Hard

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

  1. 1

    The standard first recursion; also motivates memoisation later.

    Recursion BasicsReported at: AmazonAppleMicrosoft+5
  2. 2

    A simple base case and reduction, with a bit-trick alternative.

    Recursion BasicsReported at: AmazonAppleGoogle+1
  3. 3

    Enumerating combinations of bits; a light warm-up for combinatorial search.

    EnumerationReported at: Google
  4. 4
    Pow(x, n)Medium

    Fast exponentiation by halving; O(log n) recursion.

    Divide & ConquerReported at: MetaAmazonGoogle+5
  5. 5

    Solving by relating a node to its parent, not by building the string.

    Recursion on StructureReported at: Adobe
  6. 6
    SubsetsMedium

    The base template for backtracking and bitmask enumeration.

    Subsets (Include / Exclude)Reported at: MetaAmazonGoogle+6
  7. 7

    Sort and skip equal siblings to avoid duplicates.

    Subsets + Duplicate SkippingReported at: MetaAmazonBloomberg+1
  8. 8

    Swap-based or used-array permutation generation.

    PermutationsReported at: AmazonMetaGoogle+6
  9. 9

    Duplicate handling in permutations.

    Permutations + Duplicate SkippingReported at: AmazonMicrosoft
  10. 10

    Choose k of n with an index cursor.

    CombinationsReported at: GoogleMetaAmazon+1
  11. 11

    Reuse allowed; a pruned backtracking classic.

    Combinations (Unbounded Reuse)Reported at: AmazonMetaMicrosoft+6
  12. 12

    Each element used once, with duplicate skipping.

    Combinations + Duplicate SkippingReported at: AmazonMetaBloomberg+1
  13. 13

    Bounded choice space with dual constraints.

    CombinationsReported at: Google
  14. 14

    Cartesian-product backtracking; a frequent phone-screen problem.

    Cartesian ProductReported at: AmazonMicrosoftMeta+5
  15. 15

    Generating only valid states instead of filtering them.

    Constrained GenerationReported at: MetaAmazonMicrosoft+8
  16. 16

    Binary choice per character.

    Subsets (Include / Exclude)Reported at: Microsoft
  17. 17

    Partition a string with a validity check at each cut.

    PartitioningReported at: GoogleAppleAmazon+2
  18. 18

    Partitioning with strict segment rules.

    Partitioning with ConstraintsReported at: AmazonMicrosoftMeta+1
  19. 19

    DFS on a grid with visited marking and undo.

    Grid BacktrackingReported at: AmazonMicrosoftMeta+4
  20. 20

    Shows how sorting and pruning make exponential search feasible.

    Constraint Search with PruningReported at: GoogleAmazonLinkedIn
  21. 21

    The canonical constraint-satisfaction problem.

    Constraint Search with PruningReported at: AmazonMetaMicrosoft+4
  22. 22

    Counting instead of listing; sets or bitmasks for speed.

    Constraint Search with PruningReported at: ByteDance / TikTok
  23. 23

    Full constraint propagation by backtracking.

    Constraint Search with PruningReported at: AmazonAppleGoogle+8
  24. 24

    Carries running totals and handles multiplication precedence.

    Backtracking with StateReported at: Meta
  25. 25

    Minimum removals with deduplication; asked at Meta.

    BFS / Backtracking with PruningReported at: MetaAmazon