Pattern 10: Subsets / Backtracking

Deep Dive: The Decision Tree

Subsets of [1, 2, 3]

                    []
               /          \
         [1]               []
        /    \            /    \
    [1,2]    [1]      [2]      []
    / \     / \     / \     / \
[1,2,3][1,2][1,3][1] [2,3][2] [3] []

8 leaves = 2^3 subsets. Each root-to-leaf path = one subset.

Permutations of [1, 2, 3]

                     []
              /       |       \
           [1]       [2]      [3]
          /   \    /   \   /   \
       [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
         |     |     |     |     |     |
      [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

6 leaves = 3! permutations.

Template: append (choose) -> recurse -> pop (un-choose). The pop step IS the backtracking.

---

Signal: "All subsets", "all combinations", "all permutations", "generate all valid X" Template: backtrack() in templates.py

When to Use

• "Find all subsets/combinations/permutations"
• "Generate parentheses", "solve sudoku", "N-Queens"
• Any "exhaustive search" with constraints

Three Flavors

Flavor	Question	Loop Start
Subsets	Choose any subset	for i in range(start, n)
Permutations	Arrange all	for i in range(n) with used[]
Partitions	Split into groups	for i in range(start, n) with validation

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Subsets	Phase 2.5	15 min	[ ]
Permutations	Phase 2.5	15 min	[ ]
Combination Sum	Phase 2.5	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Generate all subsets / all combinations / all permutations" of the input — the explicit "all" is the loudest signal.
• "Find every valid configuration" subject to constraints (N-Queens, Sudoku, valid parentheses, word search) — exhaustive search with pruning.
• "Partition the input into K groups / palindromes / equal-sum subsets" — recursive choose-and-undo over partition boundaries.
• Small input bounds (n ≤ 20, sometimes n ≤ 12 for permutations) with no obvious closed form — strong hint that exponential exhaustive search is the intended complexity.

Anti-signals (looks like this pattern, isn't)

• "Count the number of subsets summing to X" with n ≥ 100 — DP (subset sum), not backtracking. Counting at large n needs memoisation, not enumeration.
• "Find one valid configuration as fast as possible" when a greedy choice provably works (e.g. Activity Selection) — Greedy beats backtracking.
• "Best / optimal subset" with overlapping subproblems — DP. Backtracking would re-explore the same states exponentially.