-
回溯法代码模版
function zuhe(){ let res = [] let path = [] // 回溯函数 function backtrack(path, candidate){ // 可以加入结果集了 if (path.length === len){ res.push(path.slice()) // path.slice()拷贝一份加入结果集，不影响继续递归的数组 return } // 遍历选择 for(let i=0; i<nums.length; i++){ path.push(nums[i]) // 做选择，有时候前面要加一些跳过性语句 backtrack(path, candidate) path.pop() // 撤销选择 } } backtrack(...) return res }
-
回溯思考过程
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
-
回溯注意点
-
如何去重结果集
if(i>start && candidates[i] === candidates[i-1]) continue // 做选择之前判断是否需跳过 -
候选元素不可重复使用
for(let i=start; i<candidates.length; i++){ // 这一行还不是很明白 if(i>start && candidates[i] === candidates[i-1])continue if(candidates[i]>target) continue path.push(candidates[i]) backtrack(target-candidates[i], path, i+1) path.pop() } -
候选元素可多次使用
for(var i=start;i<candidates.length;i++){ ... backtrack(target-candidates[i],i,path) ... } -
何时可以加入结果集
- target === 0
- 当前路径长度 === 目标长度
- 当前索引 === 遍历序列最后一个元素
- 候选列表为空
何时加入结果集主要看你时如何界定一个满足题意的path
-
-
Leetcode相关题目
- 039-组合总和
- 040-组合总和2
- 077-组合
- 046-全排列
- 047-全排列2
- 078-子集
- 090-子集2
- 017-电话号码的字母组合
- 022-括号生成
