216.Combination_Sum_III(Medium).md

216. Combination Sum III (Medium)

Date and Time: Jul 29, 2024, 21:35 (EST)

Link: https://leetcode.com/problems/combination-sum-iii/

Question:

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

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

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

Walk-through:

This is very similar to previous Combination Sum and Combination Sum II. We use the same way to backtrack, but we add additional checks for these specific cases.

1. For base case, before backtrack we should check if k > n and n == 1, then we should return res[] for Example 3.

2. We need to check if total == n and len(subset) == k to satisfy the requirements of finding all valid combinations of k numbers.

3. Except of checking if total > n or len(subset) >= k, we should also checking if i > 9, then we should return, because we are only allow to use 1 <= i <= 9.

Python Solution:

May 31, 2026, [Time Taken 30m 52s]

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        # Q: Find all combinations with k numbers and each combination sum up to n
        # Return a list of all combinations
        # 1. Must use 1-9. 2. No repeated number
        # backtrack(subset, curSum, i)
        # S: base cases: 1. if len(subset) == k, if curSum != n, return
        # 2. if len(subset) == k and curSum == n, save subset into res[]
        # Otherwise, pop the last element from subset and keep iterating
        # Must restrict i+1 > i

        # TC: O(9^k), SC: O(9^k)
        res = []
        def backtrack(subset, curSum, i):
            # Base case
            if len(subset) == k:
                if curSum == n:
                    res.append(subset.copy())
                return
            # Check if i is at max
            if i == 10:
                return
            # Keep iterating
            for j in range(i, 10):
                subset.append(j)
                backtrack(subset, curSum + j, j+1)
                subset.pop()
            return

        backtrack([], 0, 1)
        return res

Time Complexity: $O(k * 2^n)$, $O(2^n)$ is the total number of combinations we can have.
Space Complexity: $O(n)$

Python Solution:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res, subset = [], []
        if k > n and n == 1:
            return res
        def backtrack(i, total):
            if total == n and len(subset) == k:
                res.append(subset.copy())
                return
            if i > 9 or total > n or len(subset) >= k:
                return
            subset.append(i)
            backtrack(i+1, total + i)
            subset.pop()
            backtrack(i+1, total)
        backtrack(1, 0)
        return res

Time Complexity: $O(k * 2^n)$, $O(2^n)$ is the total number of combinations we can have.
Space Complexity: $O(n)$

Java Solution:

Similar to Python res.append(subset.copy()), we need to res.add(new ArrayList<>(subset)) to make a copy of subset into res.

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        backtrack(k, n, 1, 0, subset, res);
        return res;
    }
    private void backtrack(int k, int n, int i, int total, List<Integer> subset, List<List<Integer>> res) {
        if (total == n && subset.size() == k) {
            res.add(new ArrayList<>(subset));
            return;
        }
        if (i > 9 || subset.size() > k || total > n) {
            return;
        }
        subset.add(i);
        backtrack(k, n, i+1, total+i, subset, res);
        subset.remove(subset.size()-1);
        backtrack(k, n, i+1, total, subset, res);
    }
}

C++ Solution:

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> subset;
        backtrack(k, n, 1, 0, subset, res);
        return res;
    }
    void backtrack(int k, int n, int i, int total, vector<int>& subset, vector<vector<int>>& res) {
        if (total == n && subset.size() == k) {
            res.push_back(subset);
            return;
        }
        if (i > 9 || subset.size() > k || total > n) {
            return;
        }
        subset.push_back(i);
        backtrack(k, n, i+1, total + i, subset, res);
        subset.pop_back();
        backtrack(k, n, i+1, total, subset, res);
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	31 ms	16.3 MB
Java	0 ms	40.6 MB
C++	0 ms	8.7 MB