Problem Statement

Combination Sum III

You have the digits 1 through 9. You need to find every way to pick exactly k of them so that they add up to n. Each digit can be used at most once, and a digit can only appear once in a combination. Return the full list of combinations that work. For example, if k is 3 and n is 7, the answer is [[1,2,4]], because 1 plus 2 plus 4 is 7, and no other group of 3 different digits adds up to 7. The tool we use is called backtracking. Backtracking is like exploring a maze: you walk down a path of choices, and the moment you hit a dead end, you back up to the last fork and try a different turn. Here, each "choice" is picking the next digit, and a "dead end" is a partial group that can no longer reach our goal.

mediumBacktrackingBacktrackingTime: O(C(9,k) * k) · Space: O(k)

Signals to notice

k numbers from 1-9 summing to nfixed count and targettiny search space

Brute force first

All C(9,k) combinations — very small.

The key insight

Backtracking: choose from [start, 9], track remaining sum. Prune aggressively. O(C(9,k)).

Trace it on `k=3, n=9`

start=1,rem=9,combo=[] -> pick 1; recurse start=2,rem=8
combo=[1,2],rem=6 -> need 1 more; pick 3,4,5 fail sum, pick 6: combo=[1,2,6],rem=0 -> record [1,2,6]
back to combo=[1],start=3,rem=8 -> pick 3; combo=[1,3],rem=5 -> pick 5: rem=0 -> record [1,3,5]
combo=[1] exhausted (4->[1,4] needs 5 then 5 dup-skipped, no hit); back to combo=[],pick 2,start=3,rem=7
combo=[2,3],rem=4 -> pick 4: rem=0 -> record [2,3,4]
combo=[] picks 3+: 3+4+5=12>9 region, i>rem breaks early -> no more
return [[1,2,6],[1,3,5],[2,3,4]]

What must stay true

The search space is at most C(9,k) — tiny. Aggressive pruning (sum > target, remaining digits < remaining slots) makes it extremely fast.

Shape of the loop

backtrack(start, remaining, combo):
  if len(combo) == k: if remaining == 0: record combo; return
  for i in start..9:
    if i > remaining: break        # prune: rest only grows
    combo.add(i); backtrack(i+1, remaining-i, combo); combo.pop()
start with backtrack(1, n, [])

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not pruning — the search space is small enough that it works anyway, but pruning makes it instant.

Backtracking Pattern