LeetCode 第二十五天 2024.8.12

1. ：递增子序列
 题目链接: 491. 非递减子序列 - 力扣（LeetCode）
应用条件：回溯

难点：

这道题的难点在于如何去重，肯定不能像我们在组合中去重那样对数组排序。而且我们是要对每一层进行去重，这一点很重要。要想明白一层的意义，每一次for循环代表着一层，for循环里面的backtracking代表深度。所以在每次for循环前面设立一个set，for循环里判断现在取的这个数在不在set里，在就不取了。这样就避免了重复问题。

个人错误：

在递归中第一个判断就加了return，导致输出结果少了好多。

思路：

class Solution:def findSubsequences(self, nums: List[int]) -> List[List[int]]:res = []if len(nums) <= 1:return resself.backtracking(nums,0,[],res)return resdef backtracking(self,nums,startindex,cur,res):if len(cur) >= 2 and cur[len(cur)-1] >= cur[len(cur)-2]:res.append(cur[:])used = set()for i in range(startindex,len(nums)):if (cur and nums[i] < cur[-1]) or nums[i] in used:continueused.add(nums[i])cur.append(nums[i])self.backtracking(nums,i+1,cur,res)cur.pop()

2. ：全排列
 题目链接: 46. 全排列 - 力扣（LeetCode）
应用条件：回溯

难点：

这道题的目的是要找到数组的全排列，所以我们不能有startindex这个参数，但如果像上一道题那样对层去重会解决不了对树杈（树的深度）去重的问题，例如会出现[1,1,1]这样的情况，所以我们要对列去重，可以直接在方法中再传入一个参数，这个参数显示应该对哪个元素再列上去重，再遍历完这一列后，再恢复元素。

个人错误：

思路：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []if len(nums) == 0:return resself.backtracking(nums,[],res,[False]*len(nums))return resdef backtracking(self,nums,cur,res,used):if len(cur) == len(nums):res.append(cur[:])return for i in range(len(nums)):if used[i]:continueused[i] = Truecur.append(nums[i])self.backtracking(nums,cur,res,used)used[i] = Falsecur.pop()

3. ：全排列 II
 题目链接: 47. 全排列 II - 力扣（LeetCode）
应用条件：回溯

难点：

这道题又要对层去重，又要对树杈去重，综合了前两道题的去重方法，就可以做出来了。

个人错误：

思路：

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:res = []if len(nums) == 0:return resself.backtracking(nums,[],res,[False]*len(nums))return resdef backtracking(self,nums,cur,res,used):if len(cur) == len(nums):res.append(cur[:])return usedd =set()for i in range(len(nums)):if used[i] or (nums[i] in usedd):continueused[i] = True usedd.add(nums[i])cur.append(nums[i])self.backtracking(nums,cur,res,used)used[i] = Falsecur.pop()