216. Combination Sum III
MediumLeetCodeGiven 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
Python
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))
Comments
No comments yet. Be the first to comment!