Description给定一组候选数（candidates）（不重复）和一个目标数（target），找出候选数中所有唯一的组合，其中候选数和为target。可以从候选人中无限次地选择相同的重复数字。注意：所有数字（包括目标）均为正整数。解决方案集不得包含重复的组合。例1：输入：candidates=[2,3,6,7]，target=7，解集为：[[7]，[2,2,3]]例2：输入：candidates=[2,3,5],target=8,解集为：[[2,2,2,2],[2,3,3],[3,5]]描述给定一个没有重复元素的候选数组和一个目标numbertarget，求出candidates中所有能使数字之和为target的组合。候选人中的数字可以无限次重复选择。解释：所有数字（包括目标）都是正整数。解决方案集不能包含重复的组合。例1：输入：candidates=[2,3,6,7]，target=7，解集为：[[7],[2,2,3]]例2：输入：candidates=[2,3,5],target=8,解集为：[[2,2,2,2],[2,3,3],[3,5]]来源：LeetCode链接：https://leetcode-cn.com/probl...版权归领口网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路是使用深度优先搜索来遍历。如果路径之和为target，则将此路径的值添加到结果数组。为了表示路径和为target，我们将当前遍历的元素中的每一个target都减去，那么当target为0时，遍历的路径就是题目要求的。首先对给定的数组进行排序，由于元素可以重复使用，所以下一次遍历的起始位置是当前位置i，而不是i+1。由于数组已经排序，如果当前元素大于目标，可以直接返回。结束条件是target为0。#-*-coding:utf-8-*-#@Author:HeRui#@CreateDate:2018-11-2818:20:58#@LastModifiedby:HeRui#@LastModifiedtime:2019-08-1807:11:56输入importListclass解决方案：defcombinationSum(self,candidates:List[int],target:int)->List[List[int]]:res=[]candidates.sort()self.dfs(candidates,target,0,[],res)returnresdefdfs(self,candidates,target,index,path,res):如果目标==0:res.append(list(path))foriinrange(index,len(candidates)):ifcandidates[i]>target:returnpath.append(candidates[i])self.dfs(candidates,target-candidates[i],i,path,res)path.pop()源代码文件在这里。?本文为原创文章，欢迎转载，转载须保留文章出处、作者信息及本声明。
