当前位置：首页 > article >正文

LEETCODE-DAY27

article 2025/9/15 3:11:03

title: LEETCODE-DAY27
date: 2024-03-18 12:55:19
tags:

今日内容：39. 组合总和、40.组合总和II、131.分割回文串

T1

class Solution:def backtracking(self,candidates,target,nums,res):if sum(nums)==target:res.append(nums.copy())returnfor i in range(len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,nums,res)nums.pop()def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res=[]self.backtracking(candidates,target,[],res)return res

超出时间限制

class Solution:def backtracking(self,candidates,target,nums,res):if sum(nums)==target:res.append(nums.copy())returnif sum(nums)> target:returnfor i in range(len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,nums,res)nums.pop()def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res=[]self.backtracking(candidates,target,[],res)return res

andidates =
[2,3,6,7]
target =
7
输出
[[2,2,3],[2,3,2],[3,2,2],[7]]
预期结果
[[2,2,3],[7]]

有重复

暴力去重

class Solution:def backtracking(self,candidates,target,nums,res):if sum(nums)==target:if sorted(nums.copy()) not in res:res.append(sorted(nums.copy()))returnif sum(nums)> target:returnfor i in range(len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,nums,res)nums.pop()def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res=[]self.backtracking(candidates,target,[],res)return res

更便捷的方法：用index

T2

class Solution:def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif index==len(candidates):returnif sum(nums)==target:if sorted(nums.copy()) not in res:res.append(sorted(nums.copy()))returnfor i in range(index,len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,index+1,nums,res)nums.pop()def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:res=[]self.backtracking(candidates,target,0,[],res)return res

candidates =
[2,5,2,1,2]
target =
5
输出
[[1,2,2],[1,1,1,2],[5]]
预期结果
[[1,2,2],[5]]

输入
candidates =
[10,1,2,7,6,1,5]
target =
8
输出
[[1,1,6],[1,1,1,5],[1,1,1,1,2,2],[1,2,5],[1,7],[1,1,2,2,2],[2,6]]
预期结果
[[1,1,6],[1,2,5],[1,7],[2,6]]

class Solution:def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif sum(nums)==target:if sorted(nums.copy()) not in res:res.append(sorted(nums.copy()))returnfor i in range(index,len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,i+1,nums,res)nums.pop()def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:res=[]self.backtracking(candidates,target,0,[],res)return res

回溯时参数应为i+1
此时超出时间限制27/176

class Solution:def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif sum(nums)==target:if sorted(nums.copy()) not in res:res.append(sorted(nums.copy()))returnfor i in range(index,len(candidates)):nums.append(candidates[i])self.backtracking(candidates,target,i+1,nums,res)nums.pop()def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:if sum(candidates)<target:return []res=[]self.backtracking(candidates,target,0,[],res)return res

超出时间限制172/176

直接对candidates排序，这样可以减少排序的次数

class Solution:def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif sum(nums)==target:res.append(nums.copy())returnfor i in range(index,len(candidates)):if candidates[i]==candidates[i-1]:continuenums.append(candidates[i])self.backtracking(candidates,target,i+1,nums,res)nums.pop()def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:if sum(candidates)<target:return []res=[]candidates.sort()self.backtracking(candidates,target,0,[],res)return res

candidates =
[2,5,2,1,2]
target =
5
输出
[[5]]
预期结果
[[1,2,2],[5]]

 def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif sum(nums)==target:res.append(nums.copy())returnfor i in range(index,len(candidates)):#if candidates[i]==candidates[i-1]:#continuenums.append(candidates[i])self.backtracking(candidates,target,i+1,nums,res)nums.pop()

输入
candidates =
[10,1,2,7,6,1,5]
target =
8
输出
[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]
预期结果
[[1,1,6],[1,2,5],[1,7],[2,6]]

问题在于i=index时多去重了

class Solution:def backtracking(self,candidates,target,index,nums,res):if sum(nums)> target:returnif sum(nums)==target:res.append(nums.copy())returnfor i in range(index,len(candidates)):if i>index and candidates[i]==candidates[i-1]:continuenums.append(candidates[i])self.backtracking(candidates,target,i+1,nums,res)nums.pop()def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:if sum(candidates)<target:return []res=[]candidates.sort()self.backtracking(candidates,target,0,[],res)return res

T3

class Solution:def isPalindrome(self,s):i=0j=len(s)-1while i<=j:if s[i] !=s[j]:return Falsei+=1j-=1return Truedef backtracking(self,s,index,path,res):if index==len(s):res.append(path)returnfor i in range(index,len(s)):if self.isPalindrome(s[index:i]):path+=s[index:i]self.backtracking(s,i,path,res)path=path[:-(i-index)]def partition(self, s: str) -> List[List[str]]:res=[]self.backtracking(s,0,[],res)return res

RecursionError: maximum recursion depth exceeded in comparison
^^^^^^^^^^^^^^^^^^^
for i in range(index,len(s)):
Line 16 in backtracking (Solution.py)

for i in range(index,len(s)):if self.isPalindrome(s[index:i]):path.append(s[index:i])self.backtracking(s,i,path,res)path.pop()else:return

仍错误

class Solution:def isPalindrome(self,s):i=0j=len(s)-1while i<=j:if s[i] !=s[j]:return Falsei+=1j-=1return Truedef backtracking(self,s,index,path,res):if index==len(s):res.append(path)returnfor i in range(index,len(s)):if self.isPalindrome(s[index:i]):path.append(s[index:i])else:continueself.backtracking(s,i+1,path,res)def partition(self, s: str) -> List[List[str]]:res=[]self.backtracking(s,0,[],res)return res

输入
s =
“a”
输出
[[“”]]
预期结果
[[“a”]]

输入
s =
“aab”
输出
[[“”,“”,“”,“a”,“a”,“”,“aa”],[“”,“”,“”,“a”,“a”,“”,“aa”],[“”,“”,“”,“a”,“a”,“”,“aa”],[“”,“”,“”,“a”,“a”,“”,“aa”]]
预期结果
[[“a”,“a”,“b”],[“aa”,“b”]]

def backtracking(self,s,index,path,res):if index==len(s):res.append(path.copy())returnfor i in range(index,len(s)):if self.isPalindrome(s[index:i]):path.append(s[index:i])self.backtracking(s,i+1,path,res)path.pop()

输入
s =
“aab”
输出
[[“”,“”,“”],[“”,“a”],[“a”,“”],[“aa”]]
预期结果
[[“a”,“a”,“b”],[“aa”,“b”]]

错误在于出现为空的情况即i=index
故i应改为i+1,这并不会造成下标溢出，因为s[index,len(s)]正好取到s最后一个元素

class Solution:def isPalindrome(self,s):i=0j=len(s)-1while i<=j:if s[i] !=s[j]:return Falsei+=1j-=1return Truedef backtracking(self,s,index,path,res):if index==len(s):res.append(path.copy())returnfor i in range(index,len(s)):if self.isPalindrome(s[index:i+1]):path.append(s[index:i+1])self.backtracking(s,i+1,path,res)path.pop()        def partition(self, s: str) -> List[List[str]]:res=[]self.backtracking(s,0,[],res)return res