Combination Sum III

---

Combination Sum III: 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

---

Try this Problem on your own or check similar problems:

1. Combination Sum
2. Combination Sum II
3. Combinations

Solution:

Java

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        helper(k, n, 0, 1, new ArrayList<>(), result);
        return result;
    }
    private void helper(int k, int n, int currentSum, int start, List<Integer> currentList, List<List<Integer>> result){
        if(currentList.size() > k) return;
        if(currentSum == n && currentList.size() == k){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = start; i <= 9; ++i){
            if(n >= currentSum + i){
                currentList.add(i);
                helper(k, n, currentSum + i, i + 1, currentList, result);
                currentList.remove(currentList.size() - 1);
            }
        }
    }
}

JavaScript

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
  const result = [];
  helper(k, n, 0, 1, [], result);
  return result;
};
function helper(k, n, currentSum, start, currentList, result) {
  if (currentList.length > k) {
    return;
  }
  if (currentSum === n && currentList.length === k) {
    result.push([...currentList]);
    return;
  }
  for (let i = start; i <= 9; ++i) {
    if (n >= currentSum + i) {
      currentList.push(i);
      helper(k, n, currentSum + i, i + 1, currentList, result);
      currentList.pop();
    }
  }
}

Python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.helper(k, n, 0, 1, [], result)
        return result

    def helper(self, k: int, n: int, currentSum: int, start: int, currentList: List[int], result: List[List[int]]):
        if len(currentList) > k:
            return
        if currentSum == n and len(currentList) == k:
            result.append(currentList[:])
            return
        for i in range(start, 10):
            if n >= currentSum + i:
                currentList.append(i)
                self.helper(k, n, currentSum + i, i + 1, currentList, result)
                currentList.pop()

C++

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;
        vector<int> currentList;
        helper(k, n, 0, 1, currentList, result);
        return result;
    }
private:
     void helper(int k, int n, int currentSum, int start, vector<int>& currentList, vector<vector<int>>& result) {
        if (currentList.size() > k) {
            return;
        }
        if (currentSum == n && currentList.size() == k) {
            result.push_back(currentList);
            return;
        }
        for (int i = start; i <= 9; ++i) {
            if (n >= currentSum + i) {
                currentList.push_back(i);
                helper(k, n, currentSum + i, i + 1, currentList, result);
                currentList.pop_back();
            }
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(k*9^k)
• Space Complexity: O(k)

---

Explanation:

Almost identical to Combination Sum with a twist that we can't reuse numbers, and we can only choose from 1..9 range and we have to have the combination of size k. Those restrictions simplify the problem. We have the same helper function with the following changes to match the problem statement:

• we return if the currentList size is larger than k since the combination size must match k
• we only loop over 1..9 range and we only choose number that doesn't add up to number larger than n when added to the currentSum
• We have start which is ever increasing when passed to next recursive calls (we can't reuse elements)

Same backtracking principles we saw in the whole backtracking series applies here too. The deepest level recursion can go is k so we have O(k) space complexity, while for time complexity we have k decisions to make and maximum of 9 choices which leads us to O(9^k*k) with k multiplier to copy every list that fulfills the above mentioned statements. For the space complexity we have O(k) since we're dealing with currentList which has at most k elements.