LC216 Combination Sum III

class Solution: 
#time O(2^N) space O(1)
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        nums = [i for i in range(1,10)]
        res = []
        def dfs(start,target,path):
            if target < 0 or len(path) > k:
                return 
            if target == 0 and len(path) == k:
                res.append(path[:])
                return 
            for i in range(start,len(nums)):
                target -= nums[i]
                if target < 0:  # optimization
                    break
                path.append(nums[i])
                dfs(i+1,target,path)
                path.pop()
                target += nums[i]
        dfs(0,n,[])
        return res