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
