代码随想录算法训练营第三十一天| 回溯算法04

491. 递增子序列

题目： 代码随想录

视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

这题需要注意的点：

1. path长度在2以上才放入最终结果

2. 需要记录已经使用过的数字，因为数组内可能存在重复数字

3. 比较递增时，是nums[i]和path[-1]比，而不是nums[i]和nums[i-1]比，因为nums[i-1]不一定在path里

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:result=[]self.backtracking(nums,0,[],result)return resultdef backtracking(self,nums,startIndex,path,result):if len(path)>1:result.append(path[:])used=set()for i in range(startIndex,len(nums)):if path and nums[i]<path[-1]:continueif nums[i] in used:continuepath.append(nums[i])used.add(nums[i])self.backtracking(nums,i+1,path,result)path.pop()

 46. 全排列

本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex

代码随想录

视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

注意点：
1. 递归终止条件，不然会无限递归

2. 对已经使用的元素进行标记

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:result=[]used=[False]*len(nums)self.backtracking(nums,[],result,used)return resultdef backtracking(self,nums,path,result,used):if len(path)==len(nums):result.append(path[:])returnfor i in range(len(nums)):if used[i]:continueused[i]=Truepath.append(nums[i])self.backtracking(nums,path,result,used)path.pop()used[i]=False

 47. 全排列II

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容： used[i - 1] == true 也行，used[i - 1] == false 也行

题目链接：代码随想录

视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

关键点：

1. if i>0 and nums[i]==nums[i-1] and not used[i-1]条件的判断是去重的关键

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:result=[]nums.sort()used=[False]*len(nums)self.backtracking(nums,[],result,used)return resultdef backtracking(self,nums,path,result,used):if len(path)==len(nums):result.append(path[:])returnfor i in range(len(nums)):if used[i]:continueif i>0 and nums[i]==nums[i-1] and not used[i-1]:continueused[i]=Truepath.append(nums[i])self.backtracking(nums,path,result,used)path.pop()used[i]=False