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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Combination Sum III

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires generating combinations of numbers that meet a specific sum.
  • The numbers can only be between 1 and 9, which limits the search space.
  • Each number can be used at most once, meaning combinations must be unique.
  • The problem can be solved using a backtracking approach to explore potential combinations.

Space and Time Complexity

Time Complexity: O(2^n) - In the worst case, we explore all combinations. Space Complexity: O(k) - Space used by the recursion stack and storage of results.

Solution

The solution utilizes a backtracking algorithm to explore all possible combinations of numbers from 1 to 9. The algorithm maintains a temporary list to record the current combination being formed and a sum to track the total. If the current combination reaches the desired length (k) and the sum equals n, it is added to the results. The backtracking function iteratively adds numbers to the combination and recursively calls itself to continue building the combination, ensuring that each number is only used once.

Code Solutions

def combinationSum3(k, n):
    def backtrack(start, path, remaining):
        if len(path) == k and remaining == 0:
            result.append(path)
            return
        for i in range(start, 10):
            if i > remaining:
                break
            backtrack(i + 1, path + [i], remaining - i)

    result = []
    backtrack(1, [], n)
    return result
← Back to All Questions