TL;DR
Backtracking over digits 1–9 with a start digit and sum/slot pruning — O(C(9,k) · k) time, O(k) space; the whole space is at most 2^9 = 512 subsets.
Approach 1 — Brute force: enumerate all 512 subsets
The universe is fixed at nine digits, so just enumerate every subset of {1..9} via a bitmask and keep those with exactly k elements summing to n. A bitmask enumeration treats each integer 0..2^9-1 as a subset: bit i set means digit i + 1 is included.
from typing import List
def combinationSum3(k: int, n: int) -> List[List[int]]:
result: List[List[int]] = []
for mask in range(1 << 9):
combo = [d for d in range(1, 10) if mask >> (d - 1) & 1]
if len(combo) == k and sum(combo) == n:
result.append(combo)
return result
Complexity: O(2^9 · 9) ≈ 4600 operations — constant, and it passes within the constraints. It has two problems. It does not scale: widen the universe to 1..30 and 2^30 is over a billion subsets. And it demonstrates no reusable technique, which is what the interviewer is looking for. The pruned search follows.
Approach 2 — Backtracking with start digit
Build combinations in strictly increasing digit order: each call gets a start digit and only considers start..9, so every subset is generated exactly once and distinctness is automatic. Track two budgets at once: numbers still to place (k - len(path)) and sum still to reach (remaining). This is standard backtracking — depth-first extension of a partial solution, undone on return.
from typing import List
def combinationSum3(k: int, n: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int, remaining: int) -> None:
if len(path) == k:
if remaining == 0:
result.append(path.copy())
return
for d in range(start, 10):
if d > remaining:
break # digits ascend: all later ones overshoot
path.append(d)
backtrack(d + 1, remaining - d)
path.pop()
backtrack(1, n)
return result
Walkthrough on k = 3, n = 7:
[1] (rem 6) → [1,2] (rem 4) → [1,2,3] rem 1 ≠ 0, reject; [1,2,4] rem 0 → record; d = 5 > 4 → break.[1,3] (rem 3) → next digit must be ≥ 4 but 4 > 3 → break. [1,4] (rem 2): 5 > 2 → break. [1,5] (rem 1): 6 > 1 → break. [1,6] (rem 0) has only 2 digits, and its child loop breaks at once (7 > 0), so nothing is recorded there.[2] (rem 5) → [2,3] (rem 2): 4 > 2 → break. [2,4] (rem 1): break. [2,5] rem 0, length 2 — dead.[3] (rem 4) → [3,4] rem 0, length 2 — dead; higher starts overshoot.
Result: [[1,2,4]].
The explored recursion tree (with the d > remaining break marking dead branches):
flowchart TD
R["start 1, rem 7"] --> A1["1 (rem 6)"]
R --> A2["2 (rem 5)"]
R --> A3["3 (rem 4)"]
A1 --> B2["1,2 (rem 4)"]
A1 --> B3["1,3 (rem 3): next digit 4 > 3, break"]
B2 --> C3["1,2,3 (rem 1): length 3, reject"]
B2 --> C4["1,2,4 (rem 0): length 3, record"]
A2 --> D3["2,3 (rem 2): 4 > 2, break"]
A3 --> E4["3,4 (rem 0): length 2, dead"]
Complexity: O(C(9,k) · k) time — the tree visits each of the C(9,k) size-k subsets at most once, copying costs k; O(k) space for path and recursion.
Approach 3 — Add the slot-capacity prune
You know exactly how many numbers are left to place, and the digits are bounded, so both sides of the branch can be tested arithmetically. With s slots left, the reachable sums from digit d onward lie between d + (d+1) + ... + (d+s-1) (the s smallest available) and 9 + 8 + ... + (10-s) (the s largest). If remaining falls outside that window, cut the branch before looping.
from typing import List
def combinationSum3(k: int, n: int) -> List[List[int]]:
result: List[List[int]] = []
path: List[int] = []
def backtrack(start: int, remaining: int) -> None:
slots = k - len(path)
if slots == 0:
if remaining == 0:
result.append(path.copy())
return
min_reach = slots * start + slots * (slots - 1) // 2 # start, start+1, ...
max_reach = slots * 9 - slots * (slots - 1) // 2 # 9, 8, ...
if remaining < min_reach or remaining > max_reach:
return # window prune: branch can never land on 0
for d in range(start, 10):
if d > remaining:
break
path.append(d)
backtrack(d + 1, remaining - d)
path.pop()
backtrack(1, n)
return result
Walkthrough on k = 4, n = 1: first call has slots = 4, min_reach = 4·1 + 6 = 10, and remaining = 1 < 10 → return immediately. The entire search is one arithmetic check — Approach 2 would have descended into [1], [1,2], [1,2,3] before giving up.
Complexity: unchanged asymptotically — O(C(9,k) · k) time, O(k) space — but dead subtrees are now rejected at their root, which is the habit that pays off when the same problem shape appears with a larger universe.
Common pitfalls
- Checking
remaining == 0 without also checking len(path) == k — k = 3, n = 3 would wrongly accept [1,2] and [3].
- Recursing with
d instead of d + 1 — digits then repeat, and [1,1,5] sneaks into k=3, n=7.
- Off-by-one in the arithmetic-series prune (
slots*(slots-1)//2 vs slots*(slots+1)//2) — derive it once from start + (start+1) + … rather than guessing.
- Forgetting that
n can be up to 60 while the max reachable sum is 9+8+…+1 = 45 — the window prune handles this for free; without it you still terminate, just slower.
Pattern takeaway
When the choice universe is small and bounded (digits, letters, board cells), brute force also works, so the value of backtracking here is the pruning: track every budget the problem gives you (count of picks and remaining sum) and compute the feasible window before descending. Asking whether the best case can still reach the target and whether the worst case can avoid overshooting it is a reusable prune for any constrained-combination search.