5、回溯算法

  回溯算法（backtracking）是一个类似枚举的搜索尝试过程，在寻找问题解的过程中，当发现不满足求解条件时，就退回一步，尝试其它路径，该算法的时间复杂度都不会低于 O(N!)，复杂的例题包括[正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching/)、[解数独](https://leetcode-cn.com/problems/sudoku-solver/)等。   在《[回溯算法详解](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban)》一文中提到，解决一个回溯问题，实际上就是一个决策树的遍历过程，需要思考三个问题：   （1）路径：已经做出的选择。   （2）选择列表：当前可以做的选择。   （3）结束条件：到达决策树底层，无法再做选择的条件。   下面是改编过的算法通用结构。 ~~~ function backtrack(路径, 选择列表): if 满足结束条件 console.log(路径) return for 选择 of 选择列表 做选择 backtrack(路径, 选择列表) 撤销选择 ~~~   面试题12[矩阵路径](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)和面试题13[机器人运动范围](https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/)。在二维方格或矩阵的运动可用回溯法解决。 ## 一、N皇后   [N皇后](https://leetcode-cn.com/problems/n-queens/)是一道经典的回溯算法题，将 n 个皇后放置在 n×n 的棋盘上，使皇后彼此之间不能相互攻击，即每个棋子所在的行、列、对角线都不能有另一个棋子。   在下面的[示例](https://codepen.io/strick/pen/JjGzMed)中，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 个物品，假设每个物品的重量都不相等，并且不可分割。期望选择几件物品，装载到背包中。在不超过背包容量的前提下，如何让背包中物品的总重量最大？   把物品依次排列，对于物品选择装或不装，然后递归余下的物品，[如下所示](https://codepen.io/strick/pen/dyGrmzw)。 ~~~ 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(); //撤销选择 } } ~~~ ## 三、全排列   [全排列](https://leetcode-cn.com/problems/permutations/)是指输出给定数字序列的全部可能的排列，假设序列中的数字都是唯一的，利用回溯算法枚举出所有排列，[如下所示](https://codepen.io/strick/pen/VweNBKd)。 ~~~ 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 位的数](https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)。将问题转换成数字排列，用递归实现。 ***** > 原文出处： [博客园-数据结构和算法躬行记](https://www.cnblogs.com/strick/category/1809992.html) 已建立一个微信前端交流群，如要进群，请先加微信号freedom20180706或扫描下面的二维码，请求中需注明“看云加群”，在通过请求后就会把你拉进来。还搜集整理了一套[面试资料](https://github.com/pwstrick/daily)，欢迎阅读。