Combination Sum Iii - Leetcode Solution

Problem Statement: Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example: Input: k = 3, n = 7 Output: [[1,2,4]]

Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]

Solution Approach: We can solve this problem using the backtracking approach, where we recursively add numbers ranging from 1 to 9 till we find a combination that adds up to the target n. We can maintain a running sum and stop whenever the running sum equals the target n. Additionally, we also need to keep track of the current combination of numbers that we are using to build the sum.

The backtracking algorithm can be summarised in the following steps:

1. Define a function that takes in the following arguments:

• k : the number of integers to be used in a combination
• n : the target sum to be achieved by the combination
• start : the starting integer value to build the combination
• current_sum : the running sum of the numbers in the current combination
• current_combination : the list of integers in the current combination
• result : the list of all valid combinations that add up to n

2. If the current combination has k integers and its sum equals n, add the combination to the result and return.

3. If the current combination has less than k integers, then we need to find the next integer to add to the combination. We can start from the starting integer, and recursively call the function with the new integer added to the combination.

4. At each recursive call, we need to increment the starting integer value by 1, and decrement the k value by 1, as we are adding one more integer to the current combination.

5. The function should terminate once we have gone through all integers from 1 to 9, or the current sum exceeds the target n.

Solution Code:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        self.generate_combinations(k, n, 1, 0, [], result)
        return result
    
    def generate_combinations(self, k, n, start, current_sum, current_combination, result):
        if len(current_combination) == k and current_sum == n:
            result.append(list(current_combination))
            return
            
        if len(current_combination) < k:
            for i in range(start, 10):
                if current_sum + i > n:
                    break
                current_combination.append(i)
                self.generate_combinations(k, n, i+1, current_sum+i, current_combination, result)
                current_combination.pop()

Complexity Analysis:

• Time Complexity: O(9^k), where 9 is the maximum number of integers that can be used and k is the number of integers to be used in a combination.
• Space Complexity: O(k), where k represents the depth of the recursion stack.

1