沧州建设厅官方网站,网站建设干货图书,公司组织机构框架图,布吉网站的建设39.组合总和
思路#xff1a;
1.确定回溯函数参数#xff1a;定义全局遍历存放res集合和单个path#xff0c;还需要 candidates数组 targetSum#xff08;int#xff09;目标和。 startIndex#xff08;int#xff09;为下一层for循环搜索的起始位置。
2.终止条件…39.组合总和
思路
1.确定回溯函数参数定义全局遍历存放res集合和单个path还需要 candidates数组 targetSumint目标和。 startIndexint为下一层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 res40. 组合总和 II
思路
1.确定回溯函数参数定义全局遍历存放res集合和单个path还需要 candidates数组 targetSumint目标和。 startIndexint为下一层for循环搜索的起始位置。
2.终止条件
当不可能再出现解(sum(path) target)return当遍历到决策树的叶子节点时(sum(path)target)时将当前结果的数组 path 放入答案数组 res中递归停止。
3.遍历过程
约束条件不可以有重复的元素递归层startindexi1同时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,i1)path.pop()backtrack(candidates, target,0)return res131. 分割回文串
思路
1.确定回溯函数参数定义全局遍历存放res集合和单个path还需要 s字符 startindexint为下一层for循环搜索的起始位置。
2.终止条件
startindexlen(s)加入path
3.遍历过程取temp s[startindex:i1]若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:i1]if temptemp[::-1]:path.append(temp)backtrack(s,i1)path.pop()else:continuebacktrack(s,0)return res
