LeetCode0039.CombinationSum【Medium】【Python】【Backtrack】问题LeetCode给定一组候选数（candidates）（不重复）和一个目标数（target），找出所有唯一组合候选人人数总和达到目标的候选人。可以从候选人中无限次地选择相同的重复数字。注意：所有数字（包括目标）均为正整数。解集不得包含重复的组合。例1：输入：candidates=[2,3,6,7],target=7,解集为：[[7],[2,2,3]]例2:input:candidates=[2,3,5],target=8,一个解集是：[[2,2,2,2],[2,3,3],[3,5]]问题是给定一个没有重复元素的数组Candidates和一个目标数target，找出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]]思维回溯模板res=[]defbacktrack(path,selectionlist):如果满足结束条件:res.append(path)returnforselectioninselectionlist:makeselectionbacktrack(path,selectionlist)undoselection作者：jeromememory链接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-tao-mo-ban-ji-ke-by-jeromememory/来源：LeetCode版权归作者所有。商业转载请联系作者授权，非商业转载请注明出处。Python3代码类解决方案：defcombinationSum(self,candidates:List[int],target:int)->List[List[int]]:n=len(candidates)ifn==0:return[]#加速剪枝速度up,不需要candidates.sort()path,res=[],[]self.dfs(candidates,0,n,path,res,target)returnresdefdfs(self,candidates,start,n,path,res,target):#1.validresult递归终止iftarget==0:res.append(path[:])returnforiinrange(start,n):tmp=target-candidates[i]#3.pruningPruningiftmp<0:break#2.backtrackandupdate回溯和更新路径path.append(candidates[i])self.dfs(candidates,i,n,path,res,tmp)path.pop()代码地址GitHub链接参考回溯算法+剪枝
