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()