回溯算法

前言

参考文章

什么是回溯算法？

  • 回溯算法（英语：backtracking）是「暴力搜索法」中的一种，所以也叫「回溯搜索法」。
  • 回溯算法是一个「类似枚举的搜索过程」，主要是在搜索过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的已选。
  • 回溯算法采用「试错思想」，尝试分步地去解决一个问题，它是一种走不通，就回头的方法。
  • 回溯算法就是在「递归」里面嵌套「循环」。
  • 回溯是递归的副产品，只要有递归就会有回溯。

回溯算法的特点

  • 难
  • 效率不高
  • 解决某些特定问题的标配

回溯算法的经典问题

回溯算法的套路

术语

  • 已选：已经做出的选择。
  • 可选：当前可以做的选择。「难点」
  • 出口：到达决策树底层，无法再做选择的条件。

这些术语在下面的全排列问题中会用到，结合代码来理解这些术语。

模板

  1. const ans = [];
  2. function backtrack(已选, 可选) {
  3.   if (出口条件满足) {
  4.     ans.push(已选);
  5.     return;
  6.   }
  7.   for (选择 of 可选) {
  8.     做选择
  9.     backtrack(已选, 可选);
  10.     撤销选择
  11.   }
  12. }

解决一个回溯问题，实际上就是树的遍历过程，「循环」+「递归」，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

分析 - 全排列问题

排列组合

我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个。那么我们当时是怎么穷举全排列的呢？比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵「回溯树」。

回溯算法 - 图1

只要从根遍历这棵树，记录已选上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在红色节点上做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

术语解释

  • [2] 就是「已选」，记录你已经做过的选择；
  • [1,3] 就是「可选」，表示你当前可以做出的选择；
  • 「出口」就是遍历到树的底层，在这里就是可选为空的时候；

回溯算法 - 图2

「已选」和「可选」就好比上图中每个节点的属性，而我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「已选」就是一个全排列。

树的遍历

回溯算法 - 图3

使用递归 recursion，可以遍历一棵树。那么，前序遍历和后序遍历在代码中如何实现呢？

  1. function traverse(root) {
  2.   for (child of root.children) {
  3.     // 前序遍历需要的操作
  4.     traverse(child);
  5.     // 后序遍历需要的操作
  6.   }
  7. }

回溯算法 - 图4

所谓的前序遍历和后序遍历，它们只是两个很有用的时间点。前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。

回溯算法 - 图5

回想我们刚才说的，「已选」和「可选」是每个节点的属性， backtrack 函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作。我们只要在前序遍历时做选择，在后序遍历时撤销选择，就能正确得到每个节点的可选和已选。

核心逻辑

  1. for (选择 of 可选) {
  2.   // 做选择
  3.   将该选择从可选中移除
  4.   已选.push(选择);
  5.   backtrack(已选, 可选);
  6.   // 撤销选择
  7.   已选.pop(选择);
  8.   将该选择再次加入可选
  9. }

参考答案

  1. var permute = function (nums) {
  2.   let ans = []; // 存放全排列
  3.   let path = []; // 存放已选（已作出的选择）
  5.   const backtracking = (nums, path) => {
  6.     if (path.length == nums.length) { // 出口
  7.       ans.push(path.slice());
  8.       return;
  9.     }
  10.     for (let i = 0; i < nums.length; i++) {
  11.       if (path.indexOf(nums[i]) !== -1) continue; // 排除不合法的选择
  12.       path.push(nums[i]); // 做选择
  13.       backtracking(nums, path); // 进入下层决策树
  14.       path.pop(); // 取消选择
  15.     }
  16.   };
  18.   backtracking(nums, path);
  19.   return ans;
  20. };
  21. /*
  22. 已选：记录在 path 中
  23. 可选：nums 中那些不存在于 path 中的元素
  24. 出口：nums 中的元素全都 path 中出现
  25. */