Basic Backtracking Questions
Six warm-ups to lock the template into muscle memory. Each one is a direct hit of one of the four canonical shapes. By the end you should be able to write the structure without looking it up.
For each one, write down your own answer to the five questions — “what’s a complete state? what choices? what’s legal? what’s the un-do? what’s the base case?” — before peeking.
1. Generate all subsets
nums = [1, 2, 3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]].
Two choices at each index: include or skip.
Time: O(2^n × n). Space: O(n) recursion.
2. Generate all permutations
nums = [1, 2, 3] → 6 orderings. Use a used[] array; at each step, pick the next unused element.
Time: O(n! × n). Space: O(n).
3. Generate all combinations (n choose k)
n = 4, k = 2 → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]. Use a start index to enforce ordering.
The n - need + 1 upper bound is a free pruning — if we need 3 more numbers and only 2 are left, stop now.
4. Generate parentheses
Generate all well-formed parenthesis strings of length 2n. Example n = 3 → ["((()))","(()())","(())()","()(())","()()()"].
State: count of open and close parentheses used so far. Legality: never close more than opened, never exceed n of each.
The legality checks open < n and close < open are pruning baked directly into the candidate generator — no need for a separate validator at the leaf.
Time: O(C(n)) where C(n) is the n-th Catalan number. Space: O(n) recursion.
5. Letter Combinations of a Phone Number
Given a digit string like "23", return every letter combination (["ad","ae","af","bd","be","bf","cd","ce","cf"]).
Tree depth = digit string length. Branching factor = letters per digit (usually 3 or 4).
Time: O(3^a × 4^b × n) where a digits map to 3 letters and b map to 4. Space: O(n).
6. Binary Watch (or any “place k items into n slots” counter)
A binary watch has 4 LEDs for hours (1, 2, 4, 8) and 6 LEDs for minutes (1, 2, 4, 8, 16, 32). Given turnedOn, return all possible times the watch could be displaying.
Decompose: pick i of the 4 hour LEDs and turnedOn - i of the 6 minute LEDs. Combinations of the hour bits sum to a candidate hour; combinations of the minute bits sum to a candidate minute. Only valid if hour < 12 and minute < 60.
A reminder that the standard combinatoric primitives are often half the algorithm. When you can express your problem as “pick k from this set,” reach for combinations (Python), next_permutation (C++), or your own combination generator from question 3 above.
Mini-quiz
Next: the ten practice problems — every backtracking template represented, with the pruning that takes each from TLE to AC.