Combination Sum III
Find all combinations of exactly k distinct digits from 1 to 9 that sum to n.
Open on LeetCode ↗Intuition
Coming off Combination Sum I and II you will track the remaining target and record a hit the moment it reaches zero. That is half a solution, and the half you dropped is the one this problem is built around. There are two constraints running at once — exactly k numbers AND a total of exactly n — and a path satisfying one is worthless without the other. For k=3, n=9 the path [9] sums perfectly and is not an answer, because it holds one digit instead of three; the path [1,2,3] has the right length and sums to 6, also not an answer. So the base case must test both together: you are done only when the path length hits k and the remainder hits zero on the same step. Everything else is a failure, including the near-misses. The same doubling applies to pruning — you can stop early when a digit already exceeds the remainder, and because the pool 1..9 is scanned in increasing order, no later digit can fit either, so you break out of the loop entirely rather than continuing. The invariant is that at every node, the path holds distinct increasing digits and remain equals n minus their sum, so both constraints stay exactly measurable without a rescan.
Two constraints that must close simultaneously — exactly k digits and sum exactly n. Checking both at the same base case is what keeps it correct; digits run 1–9 with no repeats, so the loop starts at start and recurses with d + 1.
Approach
Track length and remainder together
Carry both the running path and the remaining sum through the recursion. The base case fires when the path reaches length k; only then do you check whether the remainder is zero. Recording on remainder == 0 alone accepts short paths, and checking length alone accepts wrong sums — the two tests belong in one place so neither can be forgotten.
Use a start index for distinctness and order
The pool is 1 through 9 and each digit may be used at most once, so a level that picks i recurses from i+1. This gives distinctness and increasing order for free, which in turn means [1,2,4] is generated once rather than in all six orderings. Same forward-only trick as Combinations 77, doing double duty here.
Prune on both constraints
Break out of the loop as soon as the candidate digit exceeds the remaining sum, since the pool only grows from there and every later digit fails too. You can prune harder still — if the largest achievable sum from the digits left cannot reach the remainder, or the smallest already overshoots, the subtree is dead. With a pool this small the first break is enough, but the habit of pruning on every constraint you are tracking is what generalises.
Solution & live demo
Common pitfalls
Recording as soon as the sum hits zero
if remain == 0:
res.append(path[:])
returnif len(path) == k:
if remain == 0:
res.append(path[:])
returnA path summing to n with fewer than k digits isn't a valid answer. Both conditions must be tested at the same moment, with the length check driving the return.
Looping past 9
for d in range(start, 10 + 1):
for d in range(start, 10):
Only the digits 1 through 9 may be used. Including 10 produces combinations containing a two-digit value, which the problem forbids.
Recursing with start instead of d + 1
backtrack(start, remain - d)
backtrack(d + 1, remain - d)
Each digit may appear at most once, so the next level must begin past the one just chosen. Using start re-offers digits already in the path and generates repeats.
Edge cases
The smallest four distinct digits total 10, so the first-digit prune fires immediately and an empty list is returned without recursing.
No pair reaches 30; every path fills its k slots with a non-zero remainder, all are rejected at the base case, and the result is empty.
Only [1,2,4] satisfies both constraints; every other length-3 path is rejected for a wrong sum.
The only possibility is all nine digits summing to 45, so the answer is [[1..9]] when n is 45 and empty otherwise.