python3题解 -动态规划目标减少 | #牛群喂食#

from re import X
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param candidates int整型一维数组 
# @param target int整型 
# @return int整型二维数组
#
class Solution:
    def cowCombinationSum(self , candidates: List[int], target: int) -> List[List[int]]:
        # write code here
        # x ,target= list(map(int,input().split())),int(input())
        # x = candidates
        # x.sort()
        # n = len(x)
        # dp = [0]*n
        # res = [[0]*n]
        
        # def dfs(start,path,target):
        #     if target == 0 :
        #         res.append(path)
        #         return res
        #     for i in range(0,n):
        #         if x[i] > target:
        #             break
        #         if x[i] == target:
        #             continue
        #         path.append(x[i])
        #         dfs(i+1,path,target-x[i])
        # dfs(0,[],target)
        # return res
        candidates.sort()  
        res = []  
        
        def dfs(start, path, target):  
            if target == 0:  
                res.append(path)  
                return  
            for i in range(start, len(candidates)):  
                if candidates[i] > target:  
                    break  
                dfs(i, path + [candidates[i]], target - candidates[i])  
        
        dfs(0, [], target)  
        return res