216. Combination Sum III Medium

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

Approach

Input: Two integers k and n, requiring us to pick k distinct numbers between 1 and 9 that sum to n.

Output: Return all possible combinations (order doesn't matter, but numbers cannot be reused).

This problem belongs to Combination Backtracking problems.

• We start from 9 (because available numbers are 1~9 and can't be repeated) and try adding numbers to our path.
• Every time a number j is picked, place it in path, and update the current sum t.
• Continue recursively picking numbers j-1 and below.
• If the current path length equals k and the sum equals n, we found a valid combination, and we append it to ans.
• If the current sum goes over n, or the remaining pool of usable numbers is insufficient to achieve the sum, we prune the search branch straight away.

Three Questions of Backtracking

1. Current Operation?

   • At current index i (representing the maximum available number), attempt to choose current number j (j ∈ [i, 1]) and add into traversal path.
   • Meaning placing number j inside the array tracking choices made, indicating "I picked it".

2. Sub-problem?

   • After choosing j, continue to pick among the available downstream values (j-1 to 1) to fill the rest of the combinations.
   • Concurrently maintain the sum value tracking t, looping recursively until exactly k numbers are collected.

3. Next Sub-problem?

   • The next recursive drill runs dfs(j-1, t+j), indicating we look sequentially at components starting from j-1 and keeping record of our aggregated sum.

Pruning Conditions

• If current sum t is strictly larger than our target sum n, we can aggressively branch off and return back immediately.
• If the remaining pool of items just isn't mathematically fit enough to satisfy the remainder formula (i.e. (i - d + 1 + i) * d // 2 < n - t), prune returning.

Implementation

python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []       # Store final results
        path = []      # The current combination traversal path

        # Backtracking worker
        def dfs(i, t):
            # Pruning 1: If current accumulated payload exceeds expected sum n, prune immediately
            if t > n:
                return

            # Pruning 2: If selecting all remaining maximal allowed digits is less than what is needed to reach target n
            # Calculation logic corresponds to summing an arithmetic progression
            d = k - len(path)
            min_sum = (i - d + 1 + i) * d // 2  # The sum of numbers ranging from i-(d-1) to i
            if min_sum < n - t:
                return

            # Condition met: Handpicked exact target quantity summing neatly exactly
            if len(path) == k and t == n:
                ans.append(path.copy())
                return

            # Process candidates branching down from large digits to smallest recursively
            for j in range(i, 0, -1):
                path.append(j)            # Pick candidate `j`
                dfs(j - 1, t + j)        # Branch down selecting components with limits adjusted beneath candidate
                path.pop()               # Take pick out of consideration recursively

        dfs(9, 0)  # Recurse starting from upper bounds `9`
        return ans

javascript

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
const combinationSum3 = function(k, n) {
    const ans = [];
    const path = [];

    function dfs(i, t) {
        if (t > n) return;

        const d = k - path.length;
        if ((i - d + 1 + i) * d / 2 < n - t) return;

        if (path.length == k && t == n) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j > 0; j --) {
            path.push(j);
            dfs(j - 1, t + j);
            path.pop()
        }
    }
    dfs(9, 0);
    return ans;
};

Complexity Analysis

• Time Complexity: O(k * 9^k) (Actually O(C(9,k) * k) which is very small)
• Space Complexity: O(k)

Links

216. Combination Sum III (English)

216. 组合总和 III (Chinese)