Combination Sum III
WHAT IT SAYS
Find all combinations of k distinct digits from 1 to 9 that sum to n.
WHAT IT'S REALLY ASKING
"At any half-finished moment you know two things exactly: how many digits you still owe, and the fact that every one of them must be distinct, larger than your last pick, and at most 9. That means you can compute the smallest and largest totals you could still possibly reach. If the number you need is not inside that window, why are you still here?"
Enumerate all k-subsets of 1..9 and check the sums
O(C(9, k) * k) time — small, but blindGenerate every combination of k digits from the nine available and keep those that add to n. Be honest: with at most 126 combinations for any k, this is fast enough to submit. The reason to go further is not the runtime — it is that the pruning you are about to learn is the thing that transfers to problems where the search space is not nine digits wide.
WHERE THE WORK IS WASTED — The search descends branches whose fate is settled by arithmetic before you enter them. Two picks left and 30 still to make? The largest two distinct digits available are 9 and 8, so 17 is your ceiling — the branch is dead, provably, and yet you walk it to the bottom. Three picks left and only 3 to make? The three smallest digits above your last pick already exceed that. Every such descent is not an unlucky guess; it is work you could have refused with one comparison.
You always know the best and worst still reachable.
Stand at any node. You have r digits left to choose, they must be strictly increasing, they must be greater than your last pick d, and they cannot exceed 9. That is enough to bound the total you can still add — from both sides, exactly. The smallest possible completion is the r smallest legal digits: (d+1) + (d+2) + ... + (d+r). The largest possible completion is the r largest digits available: 9 + 8 + ... + (9-r+1). Both are closed forms; both cost you an arithmetic expression, not a search. So the set of totals that are still reachable from this node is contained in the interval [min, max]. If the remaining target falls outside that interval, then NO completion of this partial solution exists. Not 'probably none' — none. Cutting the subtree throws away nothing, because the subtree contains nothing. Notice this subsumes the pruning rule you already know. 'Running sum exceeded the target, so stop' is just the lower half of the test: the minimum reachable completion is already too big. The interval version simply adds the other end — the branch that can never reach HIGH enough — which the naive check silently ignores and pays for. One more free cut: the digits are increasing, so if the current candidate already exceeds what remains, so does every candidate after it. Break out of the loop rather than continuing, and you kill all the siblings at once.
Recurse with a floor, and test the window before descending
O(C(9, k)) upper bound, with most of the tree never enteredRecurse with (start digit, digits remaining, target remaining). Immediately return if the target remaining is below the minimum achievable sum or above the maximum achievable sum. Otherwise loop the digit from start to 9, break the moment the digit exceeds the target remaining, and recurse with (digit + 1, r - 1, target - digit). Record when both counters hit zero together.
Bound the Reachable Range
YOU'LL SEE IT AGAIN WHEN
- The remaining choices have known minimum and maximum contributions, so everything still achievable lies inside a computable interval.
- A fixed count of picks is demanded (exactly k), which turns recursion depth into a hard constraint you can do arithmetic against.
- The naive search would descend branches that are arithmetically impossible — too large to reach, or too small to matter.