leetcode 40 组合总和2

这道题不光要判断组合的顺序问题，因为数组中存在重复的元素，所以应该避免会有重复的结果。
使用47全排列的方法，先将数组进行排序，然后判断数组当前元素是否与之前元素相同，如果相同判断一下之前元素是否有遍历过马，没遍历过算是在同层的元素，如果遍历过不是同层的元素。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def dfs(i,path,result,visit,target):
            if target==0:

                result.append(path[:])
                return 
            for j in range(i,len(candidates)):
                if target-candidates[j]<0:continue
                #if len(path)>0 and path[-1]>candidates[j]:continue
                #if j>i and candidates[j]==candidates[j-1]:continue
                if j>=1 and candidates[j]==candidates[j-1] and j-1 not in visit:
                    continue
                path.append(candidates[j])
                dfs(j+1,path,result,visit+[j],target-candidates[j])
                path.pop()
        if len(candidates)==0:
            return []
        result=[]
        candidates=sorted(candidates)
        dfs(0,[],result,[],target)
        return result

通过另一种判断是否在树的同层元素有相同的，如果有则通过j是否大于初始元素判断是否是同层还是上下层，剪枝。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

        def dfs(i,path,result,target):
            if target==0:
                if path not in result:
                    result.append(path[:])
                return 
            for j in range(i,len(candidates)):
                if target-candidates[j]<0:continue
                if len(path)>0 and path[-1]>candidates[j]:continue
                if j>i and candidates[j]==candidates[j-1]:continue
                path.append(candidates[j])
                dfs(j+1,path,result,target-candidates[j])
                path.pop()
        if len(candidates)==0:
            return []
        result=[]
        candidates=sorted(candidates)
        dfs(0,[],result,target)
        return result