leetcode216. Combination Sum III

原题链接https://leetcode.com/problems/combination-sum-iii/

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
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]]

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        def backtrack(target,path,candidates):
            if target == 0 and len(path) == k:
                res.append(path[:])
                return
            for i, num in enumerate(candidates):
                if len(path) > k:
                    return
                if num > target:
                    return
                path.append(num)
                backtrack(target - num, path,candidates[i+1:])
                path.pop()
        res = []
        path = []
        candidates = [i for i in range(1, 10)]
        backtrack(n,path,candidates)
        
        return res