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.
- code
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
def dfs(target, start, path):
len_path = len(path)
if target < 0 or len_path > k: return
if len_path == k and target == 0:
res.append(path)
return
for i in range(start, 10):
dfs(target - i, i + 1, path + [i])
dfs(n, 1, [])
return res