本文共 1498 字，大约阅读时间需要 4 分钟。

与Combination Sum不同之处在candidates数组中的元素最多只能用一次，且结果集必须不含有重复元素，方法为：

当前元素跟前一个元素是相同的时候，如果前一个元素被取了，那当前元素可以被取，也可以不取，反过来如果前一个元素没有取，那我们这个以及之后的所以相同元素都不能被取。

class Solution(object):    def combinationSum2(self, candidates, target):        """        :type candidates: List[int]        :type target: int        :rtype: List[List[int]]        """        result = []        lenofcan = len(candidates)        if lenofcan == 0:            return result        currentresult = []        index = 0        candidates.sort()        self.backtracking(candidates, index, target, result, currentresult, lenofcan)        return result        def backtracking(self, candidates, index, lefttarget, result, currentresult, lenofcan):        if lefttarget == 0:            result.append(currentresult)            return                    if index > lenofcan - 1:            return                    factor = lefttarget / candidates[index]        if factor == 0:            return                copylefttarget = lefttarget        for i in range(2):            skip = 1            copycurrentresult = copy.deepcopy(currentresult)            copylefttarget = lefttarget - i * candidates[index]            if i == 1:                copycurrentresult.append(candidates[index])            if i == 0:                while index + skip < lenofcan and candidates[index] == candidates[index + skip]:                    skip += 1            self.backtracking(candidates, index + skip, copylefttarget, result, copycurrentresult, lenofcan)

转载地址：http://kmbvb.baihongyu.com/