回溯法代码模版

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相关题目

1. 039-组合总和
2. 040-组合总和2
3. 077-组合
4. 046-全排列
5. 047-全排列2
6. 078-子集
7. 090-子集2
8. 017-电话号码的字母组合
9. 022-括号生成