ProblemLeetCode给定一个候选数（candidates）和一个目标数（target）的集合，找出候选数中所有唯一的组合，其中候选数的和为target。候选数中的每个数可能只组合使用一次。注意：所有数字（包括目标）均为正整数。解决方案集不得包含重复的组合。例1：输入：candidates=[10,1,2,7,6,1,5],target=8,A解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]例2：输入：candidates=[2,5,2,1,2],target=5,Asolutionsetis:[[1,2,2],[5]]题目给定一个候选数组和一个目标数target，找出候选中所有可以使数字之和为target的组合。candidates中的每个数字在每个组合中只能使用一次。解释：所有数字（包括目标数字）都是正整数。解决方案集不能包含重复的组合。例1：输入：candidates=[10,1,2,7,6,1,5],target=8，解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]例2：输入：candidates=[2,5,2,1,2],target=5,解集为：[[1,2,2],[5]]思考回溯模板res=[]defbacktrack(path,selectionlist):如果满足结束条件:res.append(path)returnforselectioninselectionlist:makeselectionbacktrack(path,selectionlist)undoselectionPython3代码fromtypingimportListclassSolution:defcombinationSum2(self,candidates:List[int],target:int)->List[List[int]]:n=len(candidates)ifn==0:return[]#加速修剪速度，不需要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.pruningcut分支如果tmp<0:break#防止这种情况：一个数字被多次使用ifi>startandcandidates[i]==candidates[i-1]:continue#2.backtrackandupdatebacktrackandupdatepathpath.append(candidates[i])self.dfs(candidates,i+1,n,path,res,tmp)path.pop()GitHublinkPython
