Every set of k distinct digits from 1 to 9 that sums to n: pick in increasing order, track what's left, and stop once a digit is too big.
▼The problem
LeetCode 216 (Medium). Find all combinations of k distinct numbers from 1 to 9 that add up to n; each number is used at most once, and every combination appears once.
Examples (LeetCode's): k = 3, n = 7 → [[1, 2, 4]] (the one walked through), k = 3, n = 9 → [[1, 2, 6], [1, 3, 5], [2, 3, 4]], and k = 4, n = 1 → [] (the four smallest already make 1 + 2 + 3 + 4 = 10).
The solution
def combination_sum3(k, n):
res, path = [], []
def go(start, left):
if len(path) == k:
if left == 0: res.append(path[:])
return
for d in range(start, 10):
if d > left: break
path.append(d)
go(d + 1, left - d)
path.pop()
go(1, n)
return resTranscript
Combination Sum Three. Pick k different numbers from one to nine that add up to n, and return every such combination.
With k three and n seven, there's just one: one, two, four. With n nine, there are three: one two six, one three five, and two three four. And four numbers can never add up to one, so that's empty.
The slow way: try every group of k numbers and keep the ones with the right sum. For three, that's eighty-four groups, and only one works.
The key idea: it's Combinations with a sum target. Pick numbers in increasing order and track what's left. With k picked, keep them if nothing is left. And since the numbers only grow, the moment one is bigger than what's left, stop the whole loop.
In code, a helper takes the next number to try and the amount left. When the path is full, record it if nothing is left. Otherwise loop from start to nine, break when the number is too big, then push it, recurse, and pop.
On k three, n seven: pot the one, six left. Pot the two, four left. The three leaves one with the rack full: put it back. The four leaves zero: record one, two, four. The five is bigger than four: break. Every other branch breaks within two shots: eighteen in all.
At most nine choose k groups, each copied in k steps, and the recursion is only k deep.
Pick in order, track what's left, break when it's too big. That's Combination Sum Three.