算法记录 | 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