【经典LeetCode算法题目专栏分类】【第2期】组合与排列问题系列

class?Solution:

????def?combinationSum(self,?candidates:?List[int],?target:?int)?->?List[List[int]]:

????????def?DFS(candidates,target,start,track):

????????????if?sum(track)?==?target:

????????????????res.append(track.copy())

????????????????return

????????????if?sum(track)?>?target:

????????????????return

????????????for?i in?range(start,len(candidates)):

????????????????track.append(candidates[i])

????????????????DFS(candidates,target, i,?track)

????????????????track.pop()

????????res =[]

????????DFS(candidates,target,0,[])

????????return?res

class?Solution:

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

????????def?DFS(candidates,?target,start,?track):

????????????if?sum(track)?>?target:

????????????????return?

????????????if?sum(track)?==?target:

????????????????res.append(track.copy())

????????????for?i in?range(start,len(candidates)):

# 忽略掉同一层中重复的选项，上述for循环为本层的可选择列表

????????????????if?i -?1?>=?start and?candidates[i-1]?==?candidates[i]:

????????????????????continue

????????????????track.append(candidates[i])

????????????????DFS(candidates,?target,i+1,track)

????????????????track.pop()

????????res =?[]

????????candidates.sort()

????????DFS(candidates,target,0,[])

????????return?res

class?Solution:

????def?permute(self,?nums:?List[int])?->?List[List[int]]:

????????def?backtrack(nums,?track):

????????????if?len(nums)?==?len(track):

????????????????res.append(track.copy())

????????????????return

????????????for?i in?nums:

????????????????# 排除不合法的选择，即不能选择已经在track中的元素

????????????????if?i in?track:

????????????????????continue

????????????????track.append(i)

????????????????backtrack(nums,?track)

????????????????track.pop()

????????res =?[]

????????backtrack(nums,[])

????????return?res

class?Solution:

????def?permuteUnique(self,?nums:?List[int])?->?List[List[int]]:

????????def?DFS(nums,track,used):

????????????if?len(track)?==?len(nums):

????????????????res.append(track.copy())

????????????????return

????????????for?i in?range(len(nums)):????#https://leetcode-cn.com/problems/permutations-ii/solution/47-quan-pai-lie-iiche-di-li-jie-pai-lie-zhong-de-q/

????????????????#这里理解used[i - 1]非常重要

????????????# // used[i - 1] == true，说明同一树枝上nums[i - 1]使用过,在同一个递归栈内，试用过的都是Ture

????????????# // used[i - 1] == false，说明同一树层nums[i - 1]使用过，因为回溯会使上一个元素重新变为False

????????????# // 如果同一树层nums[i - 1]使用过则直接跳过

????????????????if?i >?0?and?nums[i]?==?nums[i-1]?and?used[i-1]?==?False:

????????????????????continue

????????????????if?used[i]?==?False:

????????????????????used[i]?=?True

????????????????????track.append(nums[i])

????????????????????DFS(nums,track,used)

????????????????????track.pop()

????????????????????used[i]?=?False

????????res =?[]

????????nums.sort()

????????used =?[False?for?i in?range(len(nums))]

????????DFS(nums,[],used)

????????return?res

class?Solution:

????def?subsets(self,?nums:?List[int])?->?List[List[int]]:

????????def?backtrack(nums,?track,?start):

????????????res.append(track.copy())

????????????if?start >=?len(nums):

????????????????return?

????????????for?i in?range(start,?len(nums)):

????????????????track.append(nums[i])

????????????????backtrack(nums,?track,?i +?1)

????????????????track.pop()

????????res =?[]

????????backtrack(nums,?[],?0)

????????return?res

class?Solution:

????def?subsetsWithDup(self,?nums:?List[int])?->?List[List[int]]:

????????def?backtrack(nums,?start,?track):

????????????res.append(track.copy())

????????????for?i in?range(start,?len(nums)):

????????????????if?i-1>=start and?nums[i]==nums[i-1]:?#?同层去重

????????????????????continue

????????????????track.append(nums[i])

????????????????backtrack(nums,i+1,track)

????????????????track.pop()

????????res=?[]

????????nums.sort()

????????backtrack(nums,0,[])

????????return?res

class?Solution:

????def?permutation(self,?s:?str)?->?List[str]:

????????def?backtrack(s,?cur_s):

????????????if?len(cur_s)?==?len(s):

????????????????res.append(cur_s)

????????????????return

????????????for?i in?range(len(s)):

????????????????if?i >?0?and?s[i]?==?s[i-1]?and?visited[i-1]?==?False: #同层去重

????????????????????continue

????????????????if?visited[i]?==?False:

????????????????????visited[i]?=?True

????????????????????backtrack(s,?cur_s +?s[i])

????????????????????visited[i]?=?False

????????res =?[]

????????visited =?[False?for?_ in?range(len(s))]

????????s =?''.join(sorted(list(s)))

????????backtrack(s,'')

????????return?res

写法二

class?Solution:

????def?permutation(self,?s:?str)?->?List[str]:

????????def?backtrack(s,?path):

????????????if?not?s:

????????????????res.append(path)

????????????seen =?set()

????????????for?i in?range(len(s)):

????????????????if?s[i]?in?seen:?continue ??#?同层去重

????????????????seen.add(s[i])

#传递的字符串去除了当前选择的字符s[:i]+s[i+1:]

????????????????backtrack(s[:i]+s[i+1:],?path +?s[i])

????????res =?[]

????????backtrack(s,?"")

????????return?res