LeetCode 第二十三天 2024.8.9
1. ：组合总和
题目链接: 39. 组合总和 - 力扣（LeetCode）
应用条件：回溯，递归
难点：
这道题相比之前简单的组合问题，难点在于可以重复选择，重复选择也是需要startindex的，因为如果没有startindex在递归中将会一直在第一个陷入死循环。只不过这次在for循环中的递归中把startindex从原来的i+1变成i即可包含重复选择了。
个人错误：
没记startindex，一开始忽略了sum(curlist) > target
思路：
class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:curlist = []res = []startindex = 0self.backtracking(candidates,target,curlist,res,startindex)return resdef backtracking(self,nums,target,curlist,res,startindex):if sum(curlist) > target:returnif sum(curlist) == target:res.append(curlist[:])returnfor i in range(startindex,len(nums)):curlist.append(nums[i])self.backtracking(nums,target,curlist,res,i)curlist.pop()2. ：组合总和II
题目链接: 40. 组合总和 II - 力扣（LeetCode）
应用条件：回溯
难点：
这道题最难的点在于数组中有重复元素，但在res中不让有重复的答案，所以我们需要在递归过程中对结果集元素去重。curlist相当于书的枝，for循环想到与树的层，这里要明确我们要对层去重，枝中是可以包含重复元素的。所以可以先对数组进行排列，然后在对i的for循环中，判断在i>startindex的情况下nums[i] == nums[i-1]的情况，如果满足条件就continue，注意在这里，一定是i>startindex，不能i>0,因为如果i> 0就把枝中的也去掉了。
个人错误：
思路：
class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:curist = []res = []startindex = 0candidates.sort()self.backtracking(candidates,target,curist,res,startindex)return resdef backtracking(self,nums,target,curist,res,startindex):if sum(curist) > target:returnif sum(curist) == target:res.append(curist[:])returnfor i in range(startindex,len(nums)):if i >startindex and nums[i] == nums[i-1]:continuecurist.append(nums[i])self.backtracking(nums,target,curist,res,i+1)curist.pop()3. ：分割回文串
题目链接: 131. 分割回文串 - 力扣（LeetCode）
应用条件：回溯
难点：
这道题的难点在于能否想到递归终止条件是startindex == len(s),
个人错误：
思路：
class Solution:def partition(self, s: str) -> List[List[str]]:res = []curlist = []startindex = 0self.backtracking(s,curlist,res,startindex)return resdef backtracking(self,s,curlist,res,startindex):if startindex ==len(s):res.append(curlist[:])returnfor i in range(startindex,len(s)):if s[startindex: i + 1] == s[startindex: i + 1][::-1]:curlist.append(s[startindex:i+1])self.backtracking(s, curlist, res,i+1) curlist.pop()