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.
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
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.