本文主要是介绍代码随想录｜Day27｜回溯03｜39.组合总和、40.组合总和II、131.分割回文串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
39. 组合总和
class Solution:
def combinationSum(self, candidates, target):
result = []
candidates.sort() # 需要排序
self.backtracking(candidates, target, 0, 0, [], result)
return result
def backtracking(self, candidates, target, total, startIndex, path, result):
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
if total + candidates[i] > target: #这一步剪枝很重要
continue
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()
【思考】如candidates= [2,3,6,7] target = 7。
if total + candidates[i] > target: #这一步剪枝很重要
continue
这条剪枝使得当比如出现2+2+2+2》7时，不必再往下走到total—— path.pop()这些步骤，而是到continue，再走2+2+2+3，2+2+2+6.。。节省开销
40. 组合总和ii （后补）
class Solution:
def combinationSum2(self, candidates, target):
result = []
used = [False] * len(candidates)
candidates.sort()
self.backtracking(candidates, target, 0, 0, [], result, used)
return result
def backtracking(self, candidates, target, total, start_index, path, result, used):
if total == target:
result.append(path[:])
for i in range(start_index, len(candidates)):
if total + candidates[i] > target:
break #剪枝，当和大于target时，直接进入下一个def
if i>start_index and candidates[i] == candidates[i-1] and not used[i-1]:
continue #去重
path.append(candidates[i])
total += candidates[i]
used[i] = True
self.backtracking(candidates, target, total, i+1, path, result, used)
path.pop()
total -= candidates[i]
used[i] = False
【思考】用used来去重，当used [ i-1] = 0即False 时，在同一层上重复，需要去重；当 used [ i-1] = 1即True时，在同一枝上重复，不需要去重。
131. 分割回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
self.backtracking(s, 0, [], result)
return result
def backtracking(self, s, start_index, path, result ):
if start_index == len(s):
result.append(path[:])
return
for i in range(start_index, len(s)):
if s[start_index : i+1] == s[start_index : i+1][::-1]: #判断是否为回文字符串优化写法
path.append(s[start_index : i+1])
self.backtracking(s, i+1, path, result)
path.pop()
【思考】分割问题，重点在于start_index 和 i 相当于两个指针。重点理解： 当start_index = 0, i取到1时，就可以取得s[0:2]这个字符串。
这篇关于代码随想录｜Day27｜回溯03｜39.组合总和、40.组合总和II、131.分割回文串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
