216. Combination Sum III

Description

The problem is to find all possible combinations of k numbers from 1 to 9 that add up to a given number n. Each number in the combination must be unique, and the order of numbers does not matter.

Intuition

To solve this problem, we need to explore all possible combinations of k numbers that sum up to n. A backtracking approach is suitable here as it allows us to explore each possible combination and backtrack when we reach an invalid state. We will use a recursive function to build combinations and only keep those that meet the criteria.

Approach

1. Initialization: - Prepare a list of numbers from 1 to 9. - Initialize a list to store the results.
2. Backtracking Function: - Use a recursive function that builds combinations of numbers. - Track the current combination and its sum. - If the combination has exactly k numbers and the sum equals n, add it to the result list. - If the current sum exceeds n or if the combination is not valid, terminate that branch of recursion. - Use a loop to explore all possible numbers from the current position and recursively build combinations.
3. Base Case: - If the length of the current combination is k and the sum equals n, add the combination to the results.
4. Recursion: - For each number, add it to the current combination and recursively explore further numbers.
5. Backtrack: - Remove the last number added and try the next number in sequence.

Complexity

Time Complexity:

The time complexity is O(C(9, k) * k), where C(9, k) represents the number of combinations of choosing k numbers from 9. Each combination is explored once, and the operations inside each recursive call involve adding and removing elements from the list, which takes O(k) time.

Space Complexity:

The space complexity is O(C(9, k) * k) due to the storage required for the result list and the space used by the recursion stack. The result list stores all valid combinations, and the maximum depth of the recursion stack is k.

Code

C++

class Solution {
public:
    std::vector> combinationSum3(int k, int n) {
        std::vector> result;
        std::vector combination;
        std::vector nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtrack(nums, k, n, 0, combination, result);
        return result;
    }

private:
    void backtrack(const std::vector& nums, int k, int n, int start, 
                   std::vector& combination, std::vector>& result) {
        if (combination.size() == k && n == 0) {
            result.push_back(combination);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            if (n < nums[i]) continue; // Skip if current number is greater than remaining sum
            combination.push_back(nums[i]);
            backtrack(nums, k, n - nums[i], i + 1, combination, result);
            combination.pop_back(); // Remove last element to try the next candidate
        }
    }
};

Python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def backtrack(start: int, combination: List[int], total: int):
            if len(combination) == k and total == n:
                result.append(combination[:])
                return
            for i in range(start, 9):
                if total + (i + 1) > n:
                    continue
                combination.append(i + 1)
                backtrack(i + 1, combination, total + (i + 1))
                combination.pop()

        result = []
        backtrack(0, [], 0)
        return result

Java

public class Solution {
    public List> combinationSum3(int k, int n) {
        List> result = new ArrayList<>();
        List combination = new ArrayList<>();
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtrack(nums, k, n, 0, combination, result);
        return result;
    }

    private void backtrack(int[] nums, int k, int n, int start, 
                           List combination, List> result) {
        if (combination.size() == k && n == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }
        for (int i = start; i < nums.length; ++i) {
            if (n < nums[i]) continue; // Skip if current number is greater than remaining sum
            combination.add(nums[i]);
            backtrack(nums, k, n - nums[i], i + 1, combination, result);
            combination.remove(combination.size() - 1); // Remove last element to try the next candidate
        }
    }
}

JavaScript

var combinationSum3 = function (k, n) {
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    let ans = [];
    function helper(sum, ar, i) {
        if (ar.length === k && sum === n) {
            ans.push(ar);
            return;
        }
        if (i >= n) {
            if (ar.length === k && sum === n) {
                ans.push(ar);
                return;
            }
            return;
        }
        for (let j = i; j < arr.length; j++) {
            helper(sum + arr[j], [...ar, arr[j]], j + 1);
        }
    }
    helper(0, [], 0);
    return ans;
};