PATTERN 10: Recursion & Backtracking

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this)

“At every step, make a choice, explore it, undo it, and try the next choice.”
Backtracking is DFS on decisions, not data structures.

How to Recognize This Pattern (CRITICAL)

Think Recursion / Backtracking when:
  • Problem says generate all
  • You see combinations / permutations / subsets
  • Choices branch at each step
  • Constraints must be respected
If the solution tree fans out → recursion
If wrong choices must be reverted → backtracking

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (1–10): Recursion Fundamentals

Goal: understand base case + recursive case.
  1. #
    Fibonacci Number – LC 509
  2. #
    Pow(x, n) – LC 50
  3. #
    Climbing Stairs (Recursive View First) – LC 70
  4. #
    Subsets – LC 78
  5. #
    Subsets II – LC 90
  6. #
    Permutations – LC 46
  7. #
    Permutations II – LC 47
  8. #
    Generate Parentheses – LC 22
  9. #
    Letter Combinations of a Phone Number – LC 17
  10. #
    Combinations – LC 77
After these:
You should

️ MEDIUM (11–20): Decision Tree Thinking

Write choices in English first.
  1. #
    Combination Sum – LC 39
  2. #
    Combination Sum II – LC 40
  3. #
    Palindrome Partitioning – LC 131
  4. #
    Restore IP Addresses – LC 93
  5. #
    Word Search – LC 79
  6. #
    Partition to K Equal Sum Subsets – LC 698
  7. #
    Split String Into Max Unique Substrings – LC 1593
  8. #
    Expression Add Operators – LC 282
  9. #
    Letter Tile Possibilities – LC 1079
  10. #
    All Paths From Source to Target – LC 797
Interviewers look for:
Can you

HARD (21–30): Constraint-Driven Backtracking

These test discipline and pruning.
  1. #
    N-Queens – LC 51
  2. #
    N-Queens II – LC 52
  3. #
    Sudoku Solver – LC 37
  4. #
    Word Break II – LC 140
  5. #
    Remove Invalid Parentheses – LC 301
  6. #
    Maximum Length of Concatenated String with Unique Characters – LC 1239
  7. #
    Matchsticks to Square – LC 473
  8. #
    Beautiful Arrangement – LC 526
  9. #
    Count Numbers With Unique Digits – LC 357
  10. #
    Optimal Account Balancing – LC 465
These require:
  • Smart pruning
  • Clean undo steps
  • Strong base cases

ONE NON-NEGOTIABLE RULE (IMPORTANT)

Before coding, always write:
  • Choices
  • Base case
  • Undo step
If you can’t explain that → don’t code.

Common Interview Killers

  • Missing base case
  • Forgetting to undo (backtrack)
  • Passing wrong parameters
  • Stack overflow due to bad pruning

INTERVIEW REVISION CARD — Pattern 10

1️⃣ Pattern in One Line

"At every step make a choice, explore it fully, undo it, and try the next — DFS on a decision tree."

2️⃣ Recognize It When...

  • Problem says "generate all", "find all combinations/permutations/subsets"
  • Choices branch at each step with constraints
  • Trigger words: "all possible", "enumerate", "generate", "valid arrangements"
  • Solution space is a tree of decisions

3️⃣ Don't Confuse With...

  • DP (P13) → DP counts/optimizes; backtracking generates all solutions
  • Greedy (P9) → greedy never undoes; backtracking always undoes wrong choices
  • Graph DFS (P14A) → graph DFS visits nodes; backtracking visits decision states

4️⃣ Approach in 3 Steps

  1. #
    Define: choices at each step, base case, undo step
  2. #
    Build recursion tree — prune early when constraints are violated
  3. #
    Collect results at base case

5️⃣ Invariant to Maintain

"At every recursive call, the current path is always valid — invalid paths are pruned before recursing deeper."

6️⃣ Complexity to Justify

  • Time: O(N! or 2^N) worst case depending on problem
  • Space: O(N) recursion depth + O(result size)
  • Why: Pruning reduces practical runtime significantly

7️⃣ Edge Cases to Always Check

  • Empty input — base case must handle
  • Duplicates in input — sort first, skip duplicates
  • Single element — trivial solution
  • K larger than N in combination problems
  • Forgetting to undo (backtrack) step

8️⃣ One Line to Say in Interview

"I'll use backtracking — make a choice, recurse, undo the choice. I'll prune early when constraints are violated to avoid exploring invalid branches."