491.递增子序列

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:used = [False]*len(nums)result = []nums.sort()def backtracking(nums,path,startindex,used):nonlocal resultif len(path)>1:result.append(path[:])for i in range(startindex,len(nums)):if i>0 and nums[i] == nums[i-1] and used[i-1]==False:continueelse:path.append(nums[i])used[i] = Truebacktracking(nums,path,i+1,used)path.pop()used[i] = Falsebacktracking(nums,[],0,used)return result

问题1：如何按照顺序？（一般是直接增序）

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:result = []def backtracking(nums,path,startindex):nonlocal resultif len(path) > 1:result.append(path[:])#每进入新的一层循环，都自动清空useset = set()for i in range(startindex,len(nums)):#没有在useset合集中，新加的数要比path里面的最后一个元素大#len(path) 防止溢出if (len(path)>0 and nums[i]< path[-1]) or (nums[i] in useset):continueelse:path.append(nums[i])useset.add(nums[i])backtracking(nums,path,i+1)path.pop()     backtracking(nums,[],0)return result

z代码随想录

重点：不能对集合进行排序，怎么做呢？

任何分析，都需要画个图出来观察

题目要求：

都是递增：所以有个条件就是path中最后一个数要比新加入的数小

删除同一层节点的重复元素？使用一个set存放，如果同一层里面的数存在，就跳过

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

46.全排列

组合和排列问题差别在：

排列不需要在意集合中的顺序，顺序不同也算不同

组合需要算集合中的顺序，顺序不同不算不同

所以在这里不需要节点去重。

但是需要使用used集合记录一下每个数是否取过 

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:result = []used = [False]*len(nums)def backtracking(nums,path,used):nonlocal result#终止条件if len(nums) == len(path):result.append(path[:])return #单层遍历逻辑for i in range(0,len(nums)):#如果这个数使用过的话，就跳过if used[i] == True:continueelse:path.append(nums[i])used[i] = Truebacktracking(nums,path,used)path.pop()used[i] = Falsebacktracking(nums,[],used)return result

代码随想录

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

47.全排列 II

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

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:result = []used = [False]*len(nums)nums.sort()def backtracking(nums,used,path):nonlocal resultif len(nums) == len(path):result.append(path[:])return#单层逻辑for i in range(0,len(nums)):if used[i] == True:continueelif (i>0 and nums[i] == nums[i-1] and used[i-1] == False):continueelse:path.append(nums[i])used[i] = Truebacktracking(nums,used,path)used[i] = Falsepath.pop()backtracking(nums,used,[])return result

代码随想录

重点：

记得排序啊，重复元素去重，太重要了，这个细节

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