代码随想录算法训练营第二十五天|491、非递减子序列 46、全排列 47、全排列II

目录491. 非递减子序列题目描述解题思路46. 全排列题目描述解题思路47. 全排列 II题目描述解题思路回溯法小结491. 非递减子序列题目描述给你一个整数数组nums找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。例如数组[4,6,4,7],他的非递减子序列为[4,6],[4,4],[4,7],[6,7]解题思路本题有两个大误区题目中要求的递减子序列不能对序列进行排序所以不能用求前面子集和组合的方法对其进行排序的去重方法栗如[4,6,4,7]按照前面求的方法先对其进行排序然后进行树层去重即下标为0的4包括的子序列包括了下标为2的子序列所以不对第二个4进行递归。此题不是需要连续的子序列那么下标更小的自然会囊括下标较大的相同元素的序列若为连续的子序列那么针对上面的例子结果就是[4,6],[4,7],此时就不会有树层去重因为每个相同元素他的后序子序列可能不同那么该如何对此题进行去重呢用集合去重将遍历过的元素放入集合中为什么此时不需要进行删除操作呢因为就像[4,6,4,7]的栗子4的子序列由第一个4来代替如果删除了那么又会重复进行第二个4的子序列没有达到树层去重class Solution: def findSubsequences(self, nums: List[int]) - List[List[int]]: if len(nums) 2: return [] self.path [] self.res [] self.backtracking(nums,0) return self.res def backtracking(self,nums,start): if len(self.path) 1: self.res.append(self.path[:]) if start len(nums): return uset set() for i in range(start,len(nums)): if self.path and nums[i] self.path[-1] or nums[i] in uset: continue uset.add(nums[i]) self.path.append(nums[i]) self.backtracking(nums,i1) self.path.pop()46. 全排列题目描述给定一个不含重复数字的数组nums返回其所有可能的全排列。你可以按任意顺序返回答案。例如**输入nums [1,2,3],输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]解题思路针对排列问题是不需要start因为排列的元素在不同位置是不一样的排列结果比如[1,2,3],其中[1,2,3]和[3,2,1]就是不同的排列结果但是是相同的组合结果排列和元素的顺序有关所以不能用start来限制元素因为start以前的元素也包含在结果中那么本题的逻辑就很简单用used来表示数组中排列所使用过的元素当当前used未使用时就将其加入而使用过的说明在path数组中则跳过class Solution: def permute(self, nums: List[int]) - List[List[int]]: self.path [] self.res [] self.used [False] * len(nums) self.backtracking(nums) return self.res def backtracking(self,nums): if len(self.path) len(nums): self.res.append(self.path[:]) return for i in range(len(nums)): if self.used[i] False: self.used[i] True self.path.append(nums[i]) self.backtracking(nums) self.path.pop() self.used[i] False47. 全排列 II题目描述给定一个可包含重复数字的序列nums按任意顺序返回所有不重复的全排列。**输入nums [1,1,2]输出[[1,1,2],[1,2,1], [2,1,1]]解题思路不使用排序时用used来表示当前使用的元素用uset集合来表示树层元素的去重关键的是在当前层的集合当中比如说[1,1,2]的1的第二层剩余元素是[1,2],就在剩余元素中进行去重即将添加到集合中的逻辑写入if中如果非要写在外面那么此时顺序尤其重要要先判断当前元素是否使用过对使用过的元素continue不能把使用过的元素加入到当前层的集合中相当于上述例子中将第一个1加入到集合中第二个1被集合去重去掉如此输出无结果class Solution: def permuteUnique(self, nums: List[int]) - List[List[int]]: self.path [] self.res [] self.used [False] * len(nums) self.backtracking(nums) return self.res def backtracking(self,nums): if len(self.path) len(nums): self.res.append(self.path[:]) return uset set() for i in range(len(nums)): # if self.used[i] True: # continue if nums[i] in uset: continue # uset.add(nums[i]) if self.used[i] False: self.used[i] True self.path.append(nums[i]) self.backtracking(nums) self.path.pop() self.used[i] False uset.add(nums[i])如果使用排序那么此时就和前面一样树层去重判断i 0 and nums[i] nums[i - 1] and used[i - 1] False并且当当前元素使用过时即used[i] True也进行continue回溯法小结回溯的搜索过程回溯是递归的副产品回溯法的解题过程就是模拟一个树的过程什么时候用start组合问题时需要用到start排列问题时不需要用到start如何去重树枝去重vs数层去重去掉同一层的重复保留同一树枝的重复树层去重同一for循环中相同数字保留一个其他全部跳过避免出现一模一样的组合树枝去重往下递归的树枝上不选重复的数字回溯法中一般不能进行树枝去重去重的两种方法排序used数组不排序每层set去重