491. 递增子序列
题目简述：
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
思路：
关键在去重
利用官方题解给的思路：判断当前遍历到的数字与上一次被选的数字是否相等
1. 若相等，则不能不选当前数字
2. 若不等，方可考虑不选当前数字
代码如下：
class Solution: def findSubsequences(self, nums: List[int]) -> List[List[int]]: def dfs(i, tmp): if i == len(nums): if len(tmp) >= 2: res.append(tmp[:]) # 拷贝，tmp[:]而非tmp return # 选 nums[i] if not tmp or nums[i]>=tmp[-1]: # 需满足递增 tmp.append(nums[i]) # 选nums[i] dfs(i+1, tmp) tmp.pop() # 回溯复原 # dfs(i+1, tmp+[nums[i]]) # 与以上三行等价 # 不选 nums[i]： # 只有在nums[i]不等于前一项tmp[-1]的情况下才考虑不选nums[i] # 即若nums[i] == tmp[-1]，则必考虑选nums[i]，不予执行不选nums[i]的情况 if not tmp or (tmp and nums[i] != tmp[-1]): # 避免重复 dfs(i+1, tmp) res = [] dfs(0, []) return res
46. 全排列
题目简述：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路：
不断交换，输出nums
代码如下：
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def backtrack(first = 0): # 所有数都填完了 if first == n: res.append(nums[:]) for i in range(first, n): # 动态维护数组 nums[first], nums[i] = nums[i], nums[first] # 继续递归填下一个数 backtrack(first + 1) # 撤销操作 nums[first], nums[i] = nums[i], nums[first] n = len(nums) res = [] backtrack() return res
47. 全排列II
题目简述：
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
思路：
1. 多加一个used数组记录元素使用情况
2. 利用used数组，在回溯过程中执行剪枝操作
代码如下：
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def backtrace(first,path,nums,check): if first==n: res.append(path[:]) return for i in range(n): if check[i]==1: continue if i>0 and nums[i-1]==nums[i] and check[i-1]==0: continue check[i]=1 backtrace(first+1,path+[nums[i]],nums,check) check[i]=0 n=len(nums) nums.sort() check=[0 for _ in range(n)] res=[] backtrace(0,[],nums,check) return res
总结：
1. 如何巧妙设计取值的方式和回溯的方式是一个大难点
2. 如何剪枝也是一个难点