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
class Solution:
def combinationSum3(self, 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 genuinely passes. The constraints don’t kill this one; what kills it is that it doesn’t scale (make the universe 1..30 and 2^30 is over a billion) and it teaches nothing reusable — the interviewer wants the pruned search.
Approach 2 — Backtracking with start digit
The insight: 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 textbook backtracking: depth-first extension of a partial solution, undone on return.
from typing import List
class Solution:
def combinationSum3(self, 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]].
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
The insight: 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) (take the s smallest available) and 9 + 8 + ... + (10-s) (take the s largest). If remaining falls outside that window, cut the branch before looping.
from typing import List
class Solution:
def combinationSum3(self, 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), backtracking’s value isn’t survival — brute force survives too — it’s the pruning discipline: track every budget the problem gives you (count of picks and remaining sum here) and compute the feasible window before descending. “Can the best case still reach the target, and can the worst case avoid overshooting it?” is a reusable prune for every constrained-combination search.