回溯算法（backtracking）是一个类似枚举的搜索尝试过程，在寻找问题解的过程中，当发现不满足求解条件时，就退回一步，尝试其它路径，该算法的时间复杂度都不会低于 O(N!)，复杂的例题包括正则表达式匹配、解数独等。
在《回溯算法详解》一文中提到，解决一个回溯问题，实际上就是一个决策树的遍历过程，需要思考三个问题：
（1）路径：已经做出的选择。
（2）选择列表：当前可以做的选择。
（3）结束条件：到达决策树底层，无法再做选择的条件。
下面是改编过的算法通用结构。
function backtrack(路径, 选择列表): if 满足结束条件 console.log(路径) return for 选择 of 选择列表 做选择 backtrack(路径, 选择列表) 撤销选择
面试题12 矩阵路径和面试题13 机器人运动范围。在二维方格或矩阵的运动可用回溯法解决。
一、N皇后
N皇后是一道经典的回溯算法题，将 n 个皇后放置在 n×n 的棋盘上，使皇后彼此之间不能相互攻击，即每个棋子所在的行、列、对角线都不能有另一个棋子。
在下面的示例中，N是皇后的数量，backtrack()函数是回溯过程（如下所列），isValid()函数判断是否符合选中条件。
（1）从第一个 row=0 开始。
（2）循环列并且试图在每个 column 中放置皇后。
（3）如果方格 (row, column) 在攻击范围内，那么跳过。
（4）在 (row, column) 方格上放置皇后，继续寻找下一个位置。
（5）判断 row 是否和皇后数量相同。
const N = 4; function backtrack(route, row) { if (row == N) { //结束条件 console.log(route); return; } for (let column = 0; column < N; column++) { if (!isValid(route, row, column)) continue; route[row] = column; //做选择 backtrack(route, row + 1); //下一步 route[row] = null; //撤销选择（可省略） } } //从下往上 判断row行column列放置是否合适 function isValid(route, row, column) { let leftup = column - 1, rightup = column + 1; for (let i = row - 1; i >= 0; i--) { // 逐行往上考察每一行 if (route[i] == column) // 第i行的column列有棋子 return false; if (leftup >= 0) { if (route[i] == leftup) // 考察左上对角线：第i行leftup列有棋子 return false; } if (rightup < N) { if (route[i] == rightup) // 考察右上对角线：第i行rightup列有棋子 return false; } leftup--; rightup++; } return true; }
二、0-1背包
有一个背包，背包总的承载重量是 Wkg。现在有 n 个物品，假设每个物品的重量都不相等，并且不可分割。期望选择几件物品，装载到背包中。在不超过背包容量的前提下，如何让背包中物品的总重量最大？
把物品依次排列，对于物品选择装或不装，然后递归余下的物品，如下所示。
let max = Number.MIN_VALUE, W = 100; function backtrack(route, goods) { let weight = route.length ? route.reduce((acc, cur) => acc += cur) : 0; if (weight == W || route.length == goods.length) { //结束条件 if (weight > max && weight <= W) { max = weight; } console.log(route); return; } for (let i = 0; i < goods.length; i++) { if(weight + goods[i] > W || route.indexOf(goods[i]) > -1) continue; route.push(goods[i]); //做选择 backtrack(route, goods); route.pop(); //撤销选择 } }
三、全排列
全排列是指输出给定数字序列的全部可能的排列，假设序列中的数字都是唯一的，利用回溯算法枚举出所有排列，如下所示。
function backtrack(route, nums) { if (route.length == nums.length) { //结束条件 console.log(route); return; } for (let i = 0; i < nums.length; i++) { if (route.indexOf(nums[i]) > -1) continue; route.push(nums[i]); //做选择 backtrack(route, nums); route.pop(); //撤销选择 } }
面试题17 打印从 1~n 位的数。将问题转换成数字排列，用递归实现。
