代码随想录｜Day27｜回溯03｜39.组合总和、40.组合总和II、131.分割回文串

本文主要是介绍代码随想录｜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()