Combination sum iii

class Solution:
    def __init__(self):
        self.path = []
        self.res = []
        self.currSum = 0

    def backtrack(self, k, n, start):
        if self.currSum > n:
            return None
        if len(self.path) == k:
            if self.currSum == n:
                self.res.append(self.path.copy())
            return None
        for i in range(start, 10):
            self.path.append(i)
            self.currSum += i

            self.backtrack(k, n, i + 1)

            self.currSum -= i
            self.path.pop()
        return None

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        start = 1
        self.backtrack(k, n, start)

        return self.res

Combination Sum III

Difficulty: Medium

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.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 60