组合总和 III

Problem

Find all valid combinations of \(k\) numbers that sum up to \(n\) such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7

Output: [[1,2,4]]

Explanation: 1 + 2 + 4 = 7

There are no other valid combinations.

Example 2:

Input: k = 3, n = 9

Output: [[1,2,6],[1,3,5],[2,3,4]]

Explanation: 1 + 2 + 6 = 9

1 + 3 + 5 = 9

2 + 3 + 4 = 9

There are no other valid combinations.

Example 3:

Input: k = 4, n = 1

Output: []

Explanation: There are no valid combinations.

Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

Idea

Use backtracking to build each combination one digit at a time. Pick digits in increasing order: after choosing digit \(d\), the next digit starts from \(d + 1\). This way each digit is used at most once and every combination is generated only once, so there are no duplicates.

Track the remaining sum. When the path has \(k\) digits, record it if the remaining sum is 0. Prune early: since digits are tried in increasing order, once a digit is larger than the remaining sum, every later digit is too, so stop the loop.

Time complexity: \(O(2^9 \cdot k)\), Space complexity: \(O(k)\) (at most \(2^9\) subsets of the digits 1 to 9 are explored and copying a valid combination costs \(O(k)\); the recursion depth and the current path are at most \(k\), and the output is not counted)

Pseudo Code

def combination_sum3(k, n):
    result = []
    path = []

    def backtrack(start, remain):
        if len(path) == k:
            if remain == 0:
                result.append(path[:])
            return

        for d in range(start, 10):
            if d > remain:
                break  # later digits are even larger
            path.append(d)
            backtrack(d + 1, remain - d)
            path.pop()

    backtrack(1, n)
    return result