目录
任务
491.递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
思路
根据题意，因为要求的就是和顺序有关的子序列，所以不能对原数组进行排序，那么此时就不能用之前的used的方法和i > start的方法去重了，因为这两种方法都需要对原数组进行排序。这里考虑用set横向剪枝。
- 纵向剪枝 由于是递增的，纵向剪枝去掉不符合的情况，就是比较当前值nums[i]和其父节点值path[-1]。
- 横向剪枝 局部变量set加入新增元素，在同一层级的循环中，如果已经有同样的元素，则新的这个节点剪枝，由于是局部变量，不需要显式回溯。
总体逻辑： 取一个节点，下一次再剩余序列中取，递归进行，然后根据子序列至少两个元素，做收集操作。
class Solution:
def __init__(self) -> None:
self.path = []
self.paths = []
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
return self.paths
def dfs(self,nums,start):
if len(self.path)>1:
self.paths.append(self.path[:])
size = len(nums)
uset = set()
for i in range(start,size):
if (self.path and nums[i]< self.path[-1]): # 深入时根据条件剪枝（新节点的值小于上一个节点的值）
continue
if nums[i] in uset:
continue
uset.add(nums[i]) # 横向剪枝（去重） 由于求的就是有序子序列，不能排序然后像之前那样用 i > start去重，而用局部变量set去重，又由于是局部变量，所以不需要显式回溯,set中的元素表示该层用过的元素
self.path.append(nums[i])
self.dfs(nums,i+1)
self.path.pop()
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路
由于全排列选了一个数后，其他的数都可以取，所以不是用start来进行递归驱动的。这里有两种思考的方法
- 考虑用used数组，表示已经使用的列表元素，每次都可以取没有使用的列表元素，直到某条路就已经处理完所有元素，这个条件可以用len(path)==len(nums)来表示
- 考虑用unKnownFirst哨兵的驱动方法，表示当前处理了元素的哨兵，它将原列表分为了两个部分，[0,unKnownFirst)表示已选取的部分，[unKnownFirst，size)表示为选取的部分，随着递归的进行，unKnownFirst最终等于size，即完成了一条路径的选取
# 方法1 used数组
class Solution:
def __init__(self) -> None:
self.path = []
self.paths = []
def permute(self, nums: List[int]) -> List[List[int]]:
used = [False] * len(nums)
self.dfs(nums,used)
return self.paths
def dfs(self,nums,used):
if len(self.path) == len(nums):
self.paths.append(self.path[:])
return
for i in range(0,len(nums)):
if used[i]:
continue
used[i] = True
self.path.append(nums[i])
self.dfs(nums,used)
self.path.pop()
used[i] = False
# 方法2 unKnownFirst哨兵
class Solution:
def __init__(self) -> None:
self.path = []
self.paths = []
def permute(self, nums: List[int]) -> List[List[int]]:
self.dfs(nums,0)
return self.paths
def dfs(self,nums,unKnowFirst): # unKnowFirst 为当前第unKnowFirst的位置的值选哪个
if unKnowFirst == len(nums):
self.paths.append(self.path[:])
return
for i in range(unKnowFirst,len(nums)):
nums[i],nums[unKnowFirst] = nums[unKnowFirst],nums[i]
self.path.append(nums[unKnowFirst])
self.dfs(nums,unKnowFirst+1)
self.path.pop()
nums[i],nums[unKnowFirst] = nums[unKnowFirst],nums[i]
47.全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
思路
由于包含重复元素，且需要返回不重复的全排列，所以需要去重。想到了之前组合中的去重方法，使用used数组进行横向剪枝。
class Solution:
def __init__(self) -> None:
self.path = []
self.paths = []
self.used = []
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.used = [False] * len(nums)
nums.sort()
self.dfs(nums)
return self.paths
def dfs(self,nums):
if un == len(nums):
self.paths.append(self.path[:])
return
for i in range(0,len(nums)):
if self.used[i]:
continue
if i> 0 and nums[i] == nums[i-1] and self.used[i-1] == False:
continue
self.used[i] = True
self.path.append(nums[i])
self.dfs(nums)
self.path.pop()
self.used[i] =False
心得体会
暴力递归类的题目目前做过的类型如下：
组合： start 驱动，考虑进入下一层的时候start需要为多少，如下一个数在后续元素中选取。终止条件（收集信息）是到达需求的数量k，此时即为叶子节点，此时收集一条路径的信息，used数组或者i>start条件进行横向去重，注意去重之前要排序
子集： start 驱动，考虑进入下一层的时候start需要为多少，如下一个数在后续元素中选取,终止条件是任意节点，都将它包含的路径加入到最终结果中。递增子序列是一个类子集问题，由于不能排序所以横向剪枝采用局部变量set。
分割： 对比其他的问题相对抽象，start驱动，考虑进入下一层的时候start需要为多少，如下一个分割在后续索引中选取，终止条件为分割索引到达size。[start,i]一般表示该次分割的范围区间。
排列：used驱动，每次只要没选过都可以选。或者unKnownFirst驱动，每次选取的放在unKnownFirst，然后unKnownFirst+1驱动dfs。终止条件为排列完成，len(path)len(nums) 或者 unKnownFirstlen(nums) 去重方面，同前面问题使用used数组，注意去重前需要排序。
剩余题目有时间刷：
332.重新安排行程
51. N皇后
37. 解数独