简洁的网站地图模板,网站的建设模式,资源下载类型 wordpress,赣州51人才网491. 递增子序列 题目#xff1a; 代码随想录 视频讲解#xff1a;回溯算法精讲#xff0c;树层去重与树枝去重 | LeetCode#xff1a;491.递增子序列_哔哩哔哩_bilibili 这题需要注意的点#xff1a;
1. path长度在2以上才放入最终结果
2. 需要记录已经使用过的数字 代码随想录 视频讲解回溯算法精讲树层去重与树枝去重 | LeetCode491.递增子序列_哔哩哔哩_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[:])usedset()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,i1,path,result)path.pop() 46. 全排列 本题重点感受一下排列问题 与 组合问题组合总和子集问题的区别。 为什么排列问题不用 startIndex 代码随想录 视频讲解组合与排列的区别回溯算法求解的时候有何不同| LeetCode46.全排列_哔哩哔哩_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 也行 题目链接代码随想录 视频讲解回溯算法求解全排列如何去重| LeetCode47.全排列 II_哔哩哔哩_bilibili 关键点
1. if i0 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 i0 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
