leetcode 40. 组合总和 II python

题目描述：

题解一（超时）：

采用与39leetcode 39. 组合总和 python_ganggang的博客-CSDN博客类似的方法，但是由于不允许重复使用，增加一个记录数组中元素使用情况的数组used，初始为全0.

class Solution(object):
    def combinationSum2(self, candidates, target):
        res = []
        n = len(candidates)
        path = []
        nowsum = 0
        used = [0 for i in range(n)]
        if sum(candidates) 
结果超时
 
 
题解二（通过）：
 
参考 ​​​​​​https://segmentfault.com/a/1190000024416186
 
相比方法一改进：
 
1.此题与39不同之处在于：<1>39题中的输入candidates数组中没有重复的元素，但40输入数组可能存在存在元素。<2>39题中的数组元素可复用，但40中每个元素只允许出现一次。
 
因为最终结果要求不重复，所以递归同一层中不能出现重复数字。将candidates排序，将相同的元素放在一起，快速去重。
 
 
2.由于每个元素只允许使用一次，在进入下一层的时候，起始位置从i+1开始。 
 
class Solution(object):
    def combinationSum2(self, candidates, target):
        res = []
        n = len(candidates)
        path = []
        nowsum = 0
        candidates.sort()
        used = [0 for i in range(n)]
        if sum(candidates)=idx:
                        continue
                    if used[i] == 0:
                        used[i] = 1
                        path.append(candidates[i])
                        nowsum = nowsum + candidates[i]
                        dfs(i+1, nowsum, used)
                        path.pop()
                        nowsum = nowsum - candidates[i]
                        used[i] = 0

        dfs(0,nowsum,used)
        return res
 
 
回溯算法中的leetcode 46. 全排列 python_ganggang的博客-CSDN博客和leetcode 47. 全排列 II python_ganggang的博客-CSDN博客可以作为一组对比
 
leetcode 39. 组合总和 python_ganggang的博客-CSDN博客可以作为一组对比
 
46，39中输入的数组没有重复数字，47，40输入数组允许重复数字，在输入数组有重复数字的情况中，为了保证最终结果中不出现重复，可以进行剪枝，在搜索数中，同一层不应该出现相同的元素。
 
46 47和39 40的区别在于，46 47中形如[a,b,c] [a,c,b]属于两个结果，在39 40中[a,b,c] [a,c,b]属于一个结果，因此46 47进入下一层搜索树的时候仍然从0开始，但39 40进入下一层搜索树的时候从当前位置i开始（由于40要求每个元素只使用一次，可以直接从i+1开始）
 
总结：
 
1.输入数组中每个数字只允许使用一次：使用used数组。
 
2.避免[a,b,c] [a,c,b]类的重复：进入搜索树下一层时，从当前位置i开始，前0-i被剪枝。
 
3.输入数组存在相同元素，最终结果要求不重复：对输入数组进行排序，搜索树同一层不出现相同元素。