40. 组合总和 II - 力扣(LeetCode)
思路:(剪枝前提:先将数组candidates排序)
递归参数:排序后的candidates,target,for循环的起始index,存放路径的path。
递归出口:当path的和大于target时,return;当path的和等于target时,将path加入result中,return。
单层递归逻辑:for循环遍历,起始为index:
- 去重:当i!=index且i和i-1的元素相等时,说明在相同元素中,当前元素不是第一支,应该去重。
- 将当前元素加入path中,调用递归函数,pop(回溯)
class Solution(object):def back(self,candidates,target,index,path):sumP=sum(path)if sumP>target:return if sumP==target:self.result.append(path[:])return for i in range(index,len(candidates)):if i!=index and candidates[i]==candidates[i-1]:continuepath.append(candidates[i])self.back(candidates,target,i+1,path)path.pop()def combinationSum2(self, candidates, target):candidates.sort()self.result=[]self.back(candidates,target,0,[])return self.result