Code Implementation

class Solution:
    def combinationSum3(self, k: int, n: int) -> list[list[int]]:
        res = []
        def backtrack(start, path, total):
            if len(path) == k and total == n:
                res.append(path[:])
                return
            if len(path) > k or total > n:
                return
            for i in range(start, 10):
                path.append(i)
                backtrack(i + 1, path, total + i)
                path.pop()
        backtrack(1, [], 0)
        return res
      

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

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

var combinationSum3 = function(k, n) {
    const res = [];
    function backtrack(start, path, total) {
        if (path.length === k && total === n) {
            res.push([...path]);
            return;
        }
        if (path.length > k || total > n) return;
        for (let i = start; i <= 9; i++) {
            path.push(i);
            backtrack(i + 1, path, total + i);
            path.pop();
        }
    }
    backtrack(1, [], 0);
    return res;
};
      

Problem Description

The Combination Sum III problem asks you to find all unique combinations of k numbers that add up to a given number n, using only numbers from 1 to 9. Each number can be used at most once in each combination, and the solution set must not contain duplicate combinations.

• You must select exactly k numbers.
• Each number must be from 1 to 9, inclusive.
• Each number can be used only once per combination (no repeats).
• Return all possible valid combinations in any order.

For example, if k = 3 and n = 7, the answer is [[1,2,4]] since 1 + 2 + 4 = 7 and all numbers are unique and within 1-9.

Thought Process

When approaching this problem, the first idea is often to try all possible combinations of numbers from 1 to 9 and check which ones sum to n and have exactly k elements. However, this brute-force approach is inefficient because the number of combinations grows rapidly as k increases.

To optimize, we can use backtracking—a systematic way to build up combinations and abandon them early if they can't possibly lead to a solution. Backtracking is like exploring a decision tree: at each node, we decide whether to include a number, and we stop exploring a path as soon as it becomes invalid (for example, if the sum exceeds n or the combination gets too long).

This approach avoids unnecessary work and ensures that each combination is built in a way that meets the constraints, without duplicates or repeated numbers.

Solution Approach

We'll use a backtracking algorithm to efficiently generate all valid combinations:

1. Start with an empty combination and a sum of 0.
2. Iterate numbers from 1 to 9, starting from the last number used plus one to ensure that each number is only used once and combinations are unique (no reordering).
3. Add the current number to the combination and update the sum.
4. Check for two base cases:
   • If the combination's length is k and the sum is n, add it to the results.
   • If the combination's length exceeds k or the sum exceeds n, stop exploring this path (prune the branch).
5. Recursively continue with the next number (increment the starting point to avoid using the same number again).
6. Backtrack: Remove the last number added and try the next possibility.

This method ensures we only explore valid paths and efficiently find all unique combinations.

Example Walkthrough

Let's walk through the process for k = 3 and n = 9:

1. Start with an empty list [] and total 0.
2. Try adding 1: [1], total 1.
   • Add 2: [1,2], total 3.
   • Add 3: [1,2,3], total 6. Not enough, try next number.
   • Add 4: [1,2,4], total 7. Still not enough, try next.
   • Add 5: [1,2,5], total 8.
   • Add 6: [1,2,6], total 9. Now length is 3 and total is 9, so [1,2,6] is a valid combination.
   • Backtrack and try other possibilities, e.g. [1,3,5] = 9, so add that.
3. Repeat this process for all starting numbers, always skipping numbers already used and stopping early if the sum or length is too high.
4. Final output: [[1,2,6], [1,3,5], [2,3,4]].

Each step only explores valid paths, efficiently finding all solutions.

Time and Space Complexity

Brute-force approach: Would try all subsets of 1-9, which is 2^9 = 512 possible combinations. For each, check if length is k and sum is n. This is inefficient as k grows.

Optimized backtracking approach:

• The search space is reduced by pruning: we stop as soon as the sum exceeds n or the length exceeds k.
• In the worst case, we still explore combinations of up to 9 elements, but practical performance is much better due to pruning.
• Time complexity is O(C(9, k)) (number of ways to choose k numbers from 9), since each valid combination is generated once.
• Space complexity is O(k) for the recursion stack and up to O(C(9, k) * k) for storing all results.

Summary

The Combination Sum III problem is an excellent example of how backtracking can be used to efficiently generate all valid combinations under strict constraints. By pruning invalid paths early and ensuring each number is used at most once, we avoid unnecessary work and guarantee uniqueness of combinations. The solution is elegant because it leverages the structure of the problem to minimize computation, making it both efficient and easy to understand.