Medium

Combination Sum III

LAB

Return all combinations of k distinct numbers from 1 through 9 that sum to n, sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "k": 3,
  "n": 7
}

Output
[
  [
    1,
    2,
    4
  ]
]

FUNCTION SHAPE

k: intn: int→intMatrix

SOLUTION NOTE

We apply the template. We maintain a sum_ variable for the current sum of our list curr. Our base condition is if our list has length k and the sum is n we append to res.

We iterate over all digits from i to 9. (we either don't use or have already used the digits from 1 to i-1)

We can prune when sum_ + j > n, since adding j will make it impossible to reach n as all the digits are positive. This is an optimization, it doesn't affect correctness.

Reveal reference solution +

pythonREFERENCE

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    res = []
    curr = []
    sum_ = 0

    def backtrack(i):
        nonlocal sum_
        if len(curr) == k:
            if sum_ == n:
                res.append(curr.copy())
        else:
            for j in range(i, 10):
                if sum_ + j > n:
                    break
                sum_ += j
                curr.append(j)

                backtrack(j+1)

                curr.pop()
                sum_ -= j

    backtrack(1)
    return res

TimeO(C(9,k))

SpaceO(k)

Open on LeetCode ↗