We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Combination Sum III

Number: 216

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Adobe

Problem Description

Given two integers k and n, find all valid combinations of k numbers that sum up to n, using only the numbers 1 through 9 and each number at most once. Return all possible valid combinations with no duplicates.

Key Insights

  • Use a backtracking approach to explore all potential combinations.
  • Only numbers from 1 to 9 are available.
  • Each number can be used only once.
  • The solution must consist of exactly k numbers summing to n.
  • Early pruning is possible if the current sum plus the next candidate exceeds n.

Space and Time Complexity

Time Complexity: O(2^9) in the worst-case scenario, since we are exploring subsets of 9 numbers. Space Complexity: O(k) for the recursion stack, where k is the number of elements in the combination.

Solution

We solve this problem using the backtracking algorithm. The solution involves a recursive helper function that tries to build combinations from numbers 1 through 9. At each recursive call, if the current path contains k numbers and their sum equals n, the path is added to the result. We use early pruning by checking if the running sum exceeds n, and we start with numbers greater than the last included to avoid duplicate combinations.

Code Solutions

def combinationSum3(k, n):
    result = []
    
    def backtrack(start, path, current_sum):
        # If we've chosen k numbers, check the sum.
        if len(path) == k:
            if current_sum == n:
                result.append(path.copy())
            return
        
        # Iterate through numbers from 'start' to 9.
        for num in range(start, 10):
            if current_sum + num > n:  # Early pruning.
                break
            path.append(num)
            backtrack(num + 1, path, current_sum + num)
            path.pop()  # Backtrack.

    backtrack(1, [], 0)
    return result

# Example usage:
print(combinationSum3(3, 7))  # Output: [[1,2,4]]
← Back to All Questions