回溯法代碼模版

function zuhe(){
  let res = []
  let path = []
  
  // 回溯函數(shù)
  function backtrack(path, candidate){
    // 可以加入結(jié)果集了
    if (path.length === len){
      res.push(path.slice())      // path.slice()拷貝一份加入結(jié)果集，不影響繼續(xù)遞歸的數(shù)組
      return
    }
    // 遍歷選擇
    for(let i=0; i<nums.length; i++){
      path.push(nums[i])   // 做選擇，有時(shí)候前面要加一些跳過性語句
      backtrack(path, candidate)
      path.pop()    // 撤銷選擇  
    } 
  }
  
  backtrack(...)
  return res
}

回溯思考過程

解決一個(gè)回溯問題，實(shí)際上就是一個(gè)決策樹的遍歷過程。你只需要思考 3 個(gè)問題：

• 路徑：也就是已經(jīng)做出的選擇。
• 選擇列表：也就是你當(dāng)前可以做的選擇。
• 結(jié)束條件：也就是到達(dá)決策樹底層，無法再做選擇的條件。

回溯注意點(diǎn)

• 如何去重結(jié)果集

  if(i>start && candidates[i] === candidates[i-1]) continue  // 做選擇之前判斷是否需跳過
  

• 候選元素不可重復(fù)使用

  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)   
    ...
  }
  

• 何時(shí)可以加入結(jié)果集

  • target === 0
  • 當(dāng)前路徑長度 === 目標(biāo)長度
  • 當(dāng)前索引 === 遍歷序列最后一個(gè)元素
  • 候選列表為空

  何時(shí)加入結(jié)果集主要看你時(shí)如何界定一個(gè)滿足題意的path

Leetcode相關(guān)題目

1. 039-組合總和
2. 040-組合總和2
3. 077-組合
4. 046-全排列
5. 047-全排列2
6. 078-子集
7. 090-子集2
8. 017-電話號(hào)碼的字母組合
9. 022-括號(hào)生成