491.递增子序列
题目链接
讲解链接
本题的是求自增子序列，所以不能对原数组进行排序，排完序的数组都是自增子序列了，所以不能使用之前的去重逻辑！如果仍旧使用之前的逻辑，那么当遇到数组为{4，7，6，7}这种情况时仍会使用到第二个“7”，导致结果出现重复。所以需要考虑采用集合或者哈希表来进行去重。
回溯三部曲：
1.递归函数参数及返回值：参数必须要有的就是原数组nums和确定每次递归开始位置的startindex
def backtracking(self, nums, startindex):2.递归终止条件：当path的长度大于等于2时收集结果，但是不需要return，因为要收集所有符合条件的树节点。
if len(self.path) >= 2:
self.result.append(self.path[:])3.单层搜索逻辑：重点在于如何在树层上去重，同一父节点下的同层上使用过的元素就不能再使用了，所以需要使用一个set来负责每层的去重。used只记录本层元素是否重复使用，新的一层used都会重新定义（清空），所以used只负责本层的去重，在下面不需要对其进行回溯。
used = set()
for i in range(startindex, len(nums)):
if (self.path and nums[i] < self.path[-1]) or nums[i] in used:
continue
used.add(nums[i])
self.path.append(nums[i])
self.backtracking(nums, i + 1)
self.path.pop()整体代码如下：
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, nums, startindex):
if len(self.path) >= 2: # 长度大于等于2的时候收集一个结果
self.result.append(self.path[:]) # 不需要进行return
used = set() # 用于去重的集合，在每一层递归时都会新建一个，只记录本层使用过的元素，不需要回溯
for i in range(startindex, len(nums)):
if (self.path and nums[i] < self.path[-1]) or nums[i] in used: # 如果path不为空且当前元素小于path最右边的元素，或者当前元素已经在本层被使用过，则直接进行下一轮循环
continue
used.add(nums[i]) # 将使用过的元素添加到集合中
self.path.append(nums[i])
self.backtracking(nums, i + 1)
self.path.pop()
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
self.backtracking(nums, 0)
return self.result46.全排列
题目链接
讲解链接
本题的树形结构如下所示：
回溯三部曲：
1.递归函数参数及返回值：首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合有所不同。可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题不使用startIndex，而是需要一个used数组，标记已经选择的元素。
def backtracking(self, nums, used):2.递归终止条件：因为要求的是全排列，所以当path的长度与nums长度相同时，说明到达叶子节点，此时收集结果并返回。
if len(self.path) == len(nums):
self.result.append(self.path[:])
return3.单层搜索逻辑：在排列问题中，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组就是用来记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。
for i in range(0, len(nums)):
if used[i] == True:
continue
used[i] = True
self.path.append(nums[i])
self.backtracking(nums, used)
used[i] = False
self.path.pop()整体代码如下：
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, nums, used):
if len(self.path) == len(nums): # 长度相等作为终止条件
self.result.append(self.path[:])
return
for i in range(0, len(nums)):
if used[i] == True: # used[i]为True则说明当前元素已使用过，直接跳过
continue
used[i] = True # 将使用的元素在used数组中的位置标为True
self.path.append(nums[i])
self.backtracking(nums, used)
used[i] = False # 回溯操作
self.path.pop()
def permute(self, nums: List[int]) -> List[List[int]]:
used = [False] * len(nums)
self.backtracking(nums, used)
return self.result47.全排列Ⅱ
题目链接
讲解链接
本题难点在于数组中存在重复的元素，如果像前一题来做的话结果中会有很多重复，因为在搜索过程中会将重复的元素再搜索一遍导致产生多余的结果。因此需要考虑针对这些重复元素该怎样去重。采用递增子序列问题中的集合方法来去重是可以的，代码如下：
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, nums, used):
if len(self.path) == len(nums):
self.result.append(self.path[:])
return
uset = set() # 使用集合在树层层面进行去重
for i in range(0, len(nums)):
if nums[i] in uset or used[i] == True: # 若该元素在树枝上已取过或者在集合中则跳过
continue
uset.add(nums[i]) # 将本层使用过的元素添加到集合中
used[i] = True
self.path.append(nums[i])
self.backtracking(nums, used)
used[i] = False
self.path.pop()
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
used = [False] * len(nums)
self.backtracking(nums, used)
return self.result但是使用set进行去重存在内存占用高的问题，可以将去重部分的逻辑修改为如下代码：
if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:
continue这样做的话需要先对nums数组进行排序，这样才能保证相同的元素处于相邻的位置。当used[i - 1] = False时，说明前一个元素在当前层已经使用过了，在经历了回溯过程之后从True变成了False，这种情况下对重复元素就不再进行搜索，而是直接跳过。完整代码如下：
class Solution:
def __init__(self):
self.path = []
self.result = []
def backtracking(self, nums, used):
if len(self.path) == len(nums):
self.result.append(self.path[:])
return
for i in range(len(nums)):
if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:
continue
used[i] = True
self.path.append(nums[i])
self.backtracking(nums, used)
used[i] = False
self.path.pop()
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
used = [False] * len(nums)
self.backtracking(sorted(nums), used)
return self.result
