216. Combination Sum III

MediumLeetCode

Given two integers k and n, return all possible combinations of k numbers that add up to n using numbers from 1 to 9. Each number may only be used once in the combination.

Example 1

Input: k = 3, n = 7

Output: [[1,2,4]]

Example 2

Input: k = 3, n = 9

Output: [[1,2,6],[1,3,5],[2,3,4]]

Example 3

Input: k = 4, n = 1

Output: []

Constraints

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

How to solve the problem

• Backtracking (DFS)

Code

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        def backtracking(start: int, path: List[int]):
            if len(path) == k:
                if sum(path) == n:
                    result.append(path[:])
                return
            for i in range(start, 10):
                path.append(i)
                backtracking(i+1, path)
                path.pop()
        backtracking(1, [])
        return result

Complexity

• Time complexity: O(K*C(9, k))
• Space complexity: O(K*C(9, k))