定义

回溯算法又叫“试探法”，实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

框架

可以按照3个步骤来思考这类的问题：

  1. 「路径」：记录做出的选择。
  2. 「选择列表」：通常而言，用数组存储可以选择的操作。
  3. 「结束条件」：一般而言，就是递归的结束点，也就是搜索的结束点。 ```javascript result = []

function backtrack(路径, 选择列表) { if(‘满足结束条件’) { // 这里就是对答案做更新,依据实际题目出发 result.push(路径) return } else { for(let i = 0; i < 选择列表.length; i++) { // 对一个选择列表做相应的选择

  1.         做选择
  3.         backtrack(路径, 选择列表)
  5.         // 既然是回溯算法,那么在一次分岔路做完选择后
  6.         // 需要回退我们之前做的操作
  8.         撤销选择
  9.     }
  10. }

}

  1. <a name="I1t4K"></a>
  2. ## leetcode39-组合总和
  3. ```javascript
  4. var combinationSum = function (candidates, target) {
  5.     const ans = []
  6.     var combination = function (target, combine, index) {
  7.         if (target === 0) {
  8.             ans.push(combine)
  9.             return
  10.         }
  11.         if (target < 0) return
  12.         if (index === candidates.length) return
  13.         combination(target, combine, index + 1)
  14.         if (target - candidates[index] >= 0) {
  15.             combination(target - candidates[index], [...combine, candidates[index]], index)
  16.         }
  17.     }
  18.     combination(target, [], 0)
  20.     return ans;
  21. };