算法记录 | Day27 回溯算法

39.组合总和

思路：

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• candidates数组

• targetSum（int）目标和。

• startIndex（int）为下一层for循环搜索的起始位置。

2.终止条件：

• 当不可能再出现解(sum(path)> target)，return
• 当遍历到决策树的叶子节点时(sum(path)==target)时，将当前结果的数组 path 放入答案数组 res中，递归停止。

3.遍历过程：数组可以重复，startindex从i开始

• 从当前正在考虑元素，到数组结束为止，枚举出所有可选的元素。对于每一个可选元素：
  • 选择元素：将其添加到当前数组 path 中。
  • 递归搜索：在选择该元素的情况下，继续递归选择剩下元素。
  • 撤销选择：将该元素从当前结果数组 path 中移除。

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:res = []path = []def backtrack(candidates,target,startindex):if sum(path) > target:return if sum(path) == target:return res.append(path[:])for i in range(startindex,len(candidates)):path.append(candidates[i])backtrack(candidates,target,i)path.pop()backtrack(candidates, target,0)return res

40. 组合总和 II

思路：

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• candidates数组

• targetSum（int）目标和。

• startIndex（int）为下一层for循环搜索的起始位置。

2.终止条件：

• 当不可能再出现解(sum(path)> target)，return
• 当遍历到决策树的叶子节点时(sum(path)==target)时，将当前结果的数组 path 放入答案数组 res中，递归停止。

3.遍历过程：

• 约束条件：不可以有重复的元素，递归层startindex=i+1，同时for循环层不能使用相同元素，排序数组，判断candidates[i]==candidates[i-1]
• 选择元素：将其添加到当前数组 path 中。
• 递归搜索：在选择该元素的情况下，继续递归选择剩下元素。
• 撤销选择：将该元素从当前结果数组 path 中移除。

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:res = []path = []candidates.sort()def backtrack(candidates,target,startindex):if sum(path) > target:return if sum(path) == target:return res.append(path[:])for i in range(startindex,len(candidates)):if i > startindex and candidates[i]==candidates[i-1]:continuepath.append(candidates[i])backtrack(candidates,target,i+1)path.pop()backtrack(candidates, target,0)return res

131. 分割回文串

思路：

1.确定回溯函数参数：定义全局遍历存放res集合和单个path，还需要

• s字符

• startindex（int）为下一层for循环搜索的起始位置。

2.终止条件：

• startindex>=len(s)，加入path

3.遍历过程：取temp = s[startindex:i+1]，若temp为回文串，加入path，不是直接 跳过

注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1

class Solution:def partition(self, s: str) -> List[List[str]]:res = []path = []def  backtrack(s,startindex):if startindex >= len(s):return res.append(path[:])for i in range(startindex,len(s)):temp = s[startindex:i+1]if temp==temp[::-1]:path.append(temp)backtrack(s,i+1)path.pop()else:continuebacktrack(s,0)return res