39. 组合总和
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.tracebacking(candidates, target, 0, 0, [], res)
return res
def tracebacking(self, candidates, target, total, start, path, res):
if total == target:
res.append(path[:])
return
for i in range(start, len(candidates)):
if total + candidates[i] > target:
break
path.append(candidates[i])
total += candidates[i]
self.tracebacking(candidates, target, total, i, path, res)
total -= candidates[i]
path.pop()
40.组合总和II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.tracebacking(candidates, target, 0, 0, [], res)
return res
def tracebacking(self, candidates, target, total, start, path, res):
if target == total:
res.append(path[:])
return
# 横向遍历
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i-1]: # 去重
continue
val = candidates[i]
if total + val > target: # 剪枝
break
path.append(val)
total += val
self.tracebacking(candidates, target, total, i+1, path, res) # 纵向递归
total -= val
path.pop()
131.分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
self.tracebacking(s, 0, [], res)
return res
def tracebacking(self, s, start, path, res):
if start == len(s):
res.append(path[:])
for i in range(start, len(s)):
if self.isPalindrome(s, start, i):
path.append(s[start:i+1])
self.tracebacking(s, i+1, path, res)
path.pop()
def isPalindrome(self, s, start, end):
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True