代码随想录 - Day34 - 回溯：递增子序列+排列问题
491. 递增子序列
如果有相等的整数也算递增序列
递增子序列中至少有两个元素 (遍历的时候不用遍历nums中最后一个元素)
输入：nums = [4,6,6,2,8]
输出：[[4,6],[4,6,6],[4,6,6,8],[4,6,8],[4,8],[6,6],[6,6,8],[6,8],[2,2],[2,2,8],[2,8]]
class Solution:
def backtracking(self, nums, startIndex, path, result):
if len(path) > 1:
result.append(path[:])
# 注意这里不要加return，因为要取树上的节点
uset = set() # 用set()对本层元素去重
for i in range(startIndex, len(nums)):
# 排除重复的情况，跳过递减的情况
if (path and nums[i] < path[-1]) or (nums[i] in uset):
continue
uset.add(nums[i]) # 记录这个元素在本层用过了，本层后面不能再用了
path.append(nums[i])
self.backtracking(nums, i + 1, path, result) # 递归
path.pop() # 回溯
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
result = []
self.backtracking(nums, 0, [], result)
return result
题目说了数值范围，所以还可以用哈希表去重，速度比set()快很多。
但是，个人觉得没必要，因为放在实际情况中一般不会给数值范围。
class Solution:
def backtracking(self, nums, startIndex, path, result):
if len(path) > 1:
result.append(path[:])
# 注意这里不要加return，因为要取树上的节点
used = [0] * 201 # 使用数组来进行去重操作，题目说数值范围[-100, 100]
for i in range(startIndex, len(nums)):
# 排除重复的情况，跳过递减的情况
# 这里是利用数组的下标和数组中存储的元素来进行去重
if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:
continue
used[nums[i] + 100] = 1 # 标记当前元素已经使用过
path.append(nums[i])
self.backtracking(nums, i + 1, path, result) # 递归
path.pop() # 回溯
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
result = []
self.backtracking(nums, 0, [], result)
return result
46.全排列
全排列，即[1,2]和[2,1]算作两种排列，所以这道题的result要收集所有的叶子节点nums 中的所有整数互不相同，因此无需考虑去重
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
这种题就要考虑新的问题了，即它每次的startIndex都是固定的，遇到取过的数时则需要跳过
class Solution:
def backtracking(self, nums, used, path, result):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]: # 遇到取过的数时则需要跳过
continue
used[i] = True # 取过的数设为True
path.append(nums[i])
self.backtracking(nums, used, path, result)
path.pop() # 回溯
used[i] = False # 回溯后把该数设回False
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
used = [False] * len(nums)
self.backtracking(nums, used, [], result)
return result
考虑跳过用过的数时，脑子里第一反应是dict，却忘记了用更为简单的数组也可以…
47. 全排列 II
相较于上一题，需要考虑去重的问题，dict貌似有用武之地了
输入：nums = [1,2,1]
输出：[[1,1,2], [1,2,1], [2,1,1]]
class Solution:
def backtracking(self, nums, used, path, result):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
# 要去重的是 用过且重复 的数
if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == False:
continue
if used[i] == False: # 遇到取过的数时则需要跳过
used[i] = True # 取过的数设为True
path.append(nums[i])
self.backtracking(nums, used, path, result)
path.pop() # 回溯
used[i] = False # 回溯后把该数设回False
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
result = []
used = [False] * len(nums)
nums.sort() # 提前排好序，方便后续去重
self.backtracking(nums, used, [], result)
return result
感觉今天这几道题思路好想，代码不好写，总会在一些细节上出错，需要多练习。文章来源：https://www.toymoban.com/news/detail-699014.html
以及，mermaid画图好麻烦。。文章来源地址https://www.toymoban.com/news/detail-699014.html
到了这里，关于代码随想录 - Day34 - 回溯：递增子序列+排列问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
