前端学数据结构与算法（十四）：01执行的艺术 - 回溯算法(下)
原创前端学数据结构与算法（十四）：01执行的艺术 - 回溯算法(下)
原创
前言
书接上文，上个章节从递归到回溯的做了递进式介绍，相信已经对回溯有了初步的理解，接下来主要介绍更多与回溯相关的题目，从广度上加深对其理解。
排列问题
46 - 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1, 2, 3]
输出:
[
[1,2,3],[1,3,2],[2,1,3],
[2,3,1],[3,1,2],[3,2,1]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations这个题目和之前的组合问题类似，还是可以拆解为一个树型问题，首先看下图解：
这个求解全排列问题和组合问题不同的地方在于，每一次遍历我们都需要从数字序列的开头遍历，而在进入下一层递归时，需要告知下一层我已经被访问过了。例如我们看下左侧第一颗子树，当1被访问后，进入下一层递归就只能访问2和3了，当访问了2之后，进入下一层就只能访问3了。
运用写组合回溯的框架，我们写出以下代码：
var permute = function (nums) {
const ret = []
const \_helper = (arr) => {
if (arr.length === nums.length) {
ret.push([...arr])
return
}
for (let i = 0; i < nums.length; i++) {
arr.push(nums[i])
\_helper(arr)
arr.pop()
}
}
\_helper([])
return ret
};结果是这样的：
[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],
[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],
[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],
[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]打印出了所有的排列，一颗完全没有限制的执行树。需要加上限制，让已经访问的过的节点，下一层递归无法访问到，如果每一次都遍历当前的排列里是否有当前正在访问的元素，效率太慢了。我们增加一个used数组，用来标记已经被访问到的元素。更改代码如下：
var permute = function (nums) {
const ret = []
const used = new Array(nums.length).fill(false)
const \_helper = (arr) => {
if (arr.length === nums.length) {
ret.push([...arr])
return
}
for (let i = 0; i < nums.length; i++) {
if (!used[i]) { // 如果上一层没有访问过
used[i] = true // 标记已经访问过，带入下一层
arr.push(nums[i]) // 将当前元素加入排列里
\_helper(arr)
used[i] = false // 这一次循环执行完，重新值为false
arr.pop() // 且将其弹出
}
}
}
\_helper([])
return ret
};这段代码的执行顺序非常巧妙，大家自己可以debugger进行一步步的领略。
子集问题
78 - 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
类似于组合问题，不过是需要打印出整颗执行树的节点，空数组是每个数组的子集。还是用回溯法，优先遍历完一棵树，然后在遍历下一颗子树时将起始的位置后移一位即可，因为每个节点肯定是原始数组的子集，最大的子集也就是自身，所以不用做什么限制。
代码如下：
var subsets = function (nums) {
const ret = []
const \_helper = (start, arr) => {
ret.push([...arr]) // 没有任何限制，每个节点都是子集
for (let i = start; i < nums.length; i++) {
arr.push(nums[i])
\_helper(i + 1, arr) // i + 1每次后移，之后的递归不访问更小的节点值
arr.pop()
}
}
\_helper(0, [])
return ret
};分割问题
93 - 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），
整数之间用 '.' 分隔。
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses这是个新的类型，说的详细些。分割的过程还是使用回溯，当某一个地址的拼接不符合ip地址时，我们就即可尝试另外一种可能性即可，不过这个拼接有两个显著的规则，正好也可以作为我们递归的结束条件：
- 每一个小数点之间最多只能有三位数字，且它们的值不能大于255。
- 一共只能使用三个小数点，使用完毕之后如果还没合法的
IP，那就拼不出来。
根据这个思路我们尝试画出递归执行图：
这个递归树太庞大，画全放弃，暂且看左侧的树，思路的话就是根据左侧的树，首先尝试一位的截取，当不满足时就回退到上一层树进行两位的截取，逐渐括扩大截取的范围进行尝试，使用这几个规则，我们首先写出第一版的代码：
var restoreIpAddresses = function (s) {
const ret = []
const \_helper = (dot, start, ip) => {
if (dot === 0) { // 点用完
if (start === s.length) { // 且截取到最后一位
ret.push(ip) // 找到合法IP
}
return
}
for (let i = 1; i < 4; i++) { // 最多只能截取三位字符，所以 < 4
const val = +s.slice(start, start + i) // 截取三种子节点出来
if (val <= 255) { // 必须是小于255才行，否则过滤
\_helper(dot - 1, start + i, ip + val + (dot === 1 ? '' : '.'))
// 递归进入下一层，小数点 - 1
// 当前位置 + 1
// 有小数点就拼接小数点，最后拼接空字符串
}
}
}
\_helper(4, 0, '')
return ret
};初始化传入三个变量，dot表示剩余的小数点，每层递归使用一个，为0时结束递归；第二个变量start，用于表示当前截取字符串的位置，只有截取到最后一位且没有小数点时，才能说是找到了一个合法的IP；第三个为空字符串，为初始化用于拼接的IP地址。
虽然说递归树庞杂，但最多只能使用三个小数点，所以这颗树最多也只有4层；规则是每一层只能截取最多三位字符，所以每个节点最多是有三个子节点。分析一通，提交代码：
缺失对0x或0xx边界的情况组合的处理，这样组合必然是不合法的，我们就这个特例画出递归树来一看究竟：
在for循环里增加边界情况的处理：
for (let i = 1; i < 4; i++) {
if (i !== 1 && s[start] === "0") { // 只要是已经使用了0，再和任何数拼接都是不合法
break;
}
const val = +s.slice(start, start + i);
if (val <= 255) {
\_helper(start + i, dot - 1, ip + val + (dot === 1 ? "" : "."));
}
}此时就可以获得通过了，你以为仅此而已么，当然没这么简单，如果面试遇到这道题目，最终获得通过只能是及格而已。这题主要考察的是回溯中的剪枝问题，算法能优化到哪。递归终止条件不仅仅是前面两条，其实还有一条：
- 需要截取的字符长度必须在
4到12位之间，不然分割不出合法的IP。
被分割之后的字符同样适用这个条件，加上这个递归终止条件，我们之前的递归树，第一步就可以提前终止。整个字符串是25525511135，使用一个小数点后分割出字符2，剩下的5525511135长度大于小数点\*3，已经不可能分割出合法的地址，这是其中可以剪枝的部分。还有一个剪枝的操作就是如果start + i > s.length，可以剪枝，完整代码如下：
const restoreIpAddresses = (s) => {
if (s.length < 4 || s.length > 12) {
return [];
}
const ret = [];
const \_helper = (start, dot, ip) => {
if (dot === 0) {
if (start === s.length) {
ret.push(ip);
}
return;
}
if (s.length - start < dot || s.length - start > 3 \* dot) { // 剪枝
return;
}
for (let i = 1; i < 4; i++) {
if (start + i > s.length) { // 剪枝
break;
}
if (i !== 1 && s[start] === "0") { // 边界
break;
}
const val = +s.slice(start, start + i);
if (val <= 255) {
\_helper(start + i, dot - 1, ip + val + (dot === 1 ? "" : "."));
}
}
};
\_helper(0, 4, "");
return ret;
};floodFill染色问题
200 - 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands一道经典的DFS和BFS问题，在一个二维矩阵中找到所有的岛屿，在矩阵上查找的会麻烦一些。为什么说叫它染色问题，我们可以假设矩阵里的1就是一个凹槽，将颜料倒入其中一个节点时，它的上下左右的凹槽会被扩散的同样染色。
染色都是以一个节点作为起始，然后去扩散它的上下左右，再以它的周围节点用同样的规则进行染色，这是一个相同的问题。
所以我们的思路就是需要一个递归函数，它的作用是将扩散点设置为0，表示该节点已经被染色，然后它的上下左右执行相同的递归逻辑，直到起始点的递归调用结束，这时所有相连的1全部都会被设置为0，也表示找到了一块岛屿，岛屿数量+ 1即可。深度优先染色图如下：
本题看似复杂，其实代码逻辑比之前的回溯问题都清晰易懂，代码如下：
var numIslands = function (grid) {
const m = grid.length // 矩阵的列
const n = grid[0].length // 矩阵的行
let res = 0
const dfs = (i, j) => {
if (i < 0 || j < 0 || i >= m || j >= n) { // 如果越界，就返回
return
}
if (grid[i][j] === '0') { // 遇到了水就返回
return
}
grid[i][j] = '0' // 标记为以染色
dfs(i, j - 1) // 左
dfs(i - 1, j) // 上
dfs(i, j + 1) // 右
dfs(i + 1, j) // 下
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) { // 遍历矩阵的每个点
if (grid[i][j] === '1') { // 遇到1就开始深度优先搜索
dfs(i, j)
res++
}
}
}
return res
}棋盘问题
51 - N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
输入：4
输出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
大名鼎鼎的n皇后问题，往细了说可以单独作为一章。简单来说就是国际象棋里的皇后(Queen)因为可以攻击棋盘中所在的横线、竖线、以及两条对角线的缘故，问给你一个n \* n的棋盘，放置n个不能互相攻击的皇后，有多少种摆放方式。
看似问题是在一个棋盘里找解，其实也是一个树型问题，每一层节点的数量就是棋盘的大小，至于下一行能放置的位置，就需要根据之前皇后的位置决定，从而有剪枝的操作。
我们以有解的最小棋盘4 \* 4为例，这个问题可以抽象的理解为在第一行的每一格分别尝试放置皇后，然后它能摆放方式是怎么样的。这就是一个暴力回溯搜索的过程，在每一行放置了一个皇后之后，就需要把她的攻击范围在棋盘里进行标记，下一行的皇后就不能放在之前皇后的攻击范围内。以下展示4 \* 4找到其中一个解的过程：
如何快速的确认当前点是否能被放置是这个问题的难点，行和列的攻击范围这个好知道，难点是在于两个对角线的攻击范围怎么确认，其实这个也有规律，我们把这个棋盘的行列坐标标记在棋盘上可以发现：
在一个n \* n的棋盘里，一定会有2n - 1条对角线，两个对角线是否在攻击范围的状态，可以分别使用两个数组进行存储。从右往左的对角线在数组里的下标就是行 + 列，而从左往右的对角线在数组里的下标就是行 - 列 + n - 1，为了方便从数组0开始统计。
所以每在一行放置了一个皇后之后，就需要把她的攻击范围进行记录，在放置之后的皇后时，就需要满足两个条件：不能与之前的所有皇后在同一列，不能在之前所有皇后的两条对角线的攻击范围内。如果搜索到最后没位置可放，那就需要回溯到之前其他空的位置进行尝试，且恢复因此次放置而设置的状态值。代码如下：
var solveNQueens = function (n) {
const res = []; // 放置所有棋盘
const col = []; // 初始化列的状态
const dia1 = []; // 初始化从右往左的对角线状态
const dia2 = []; // 初始化从左往右的对角线状态
const \_helper = (rowIdx, row) => {
if (rowIdx === n) { // 最后一行放置完，找到了一个棋盘
res.push(generateBoard(row)); // 生成一个新棋盘返回
return;
}
for (let colIdx = 0; colIdx < n; colIdx++) {
if (
!col[colIdx] && // 列不在攻击范围
!dia1[rowIdx + colIdx] && // 从右往左对角线不在攻击状态
!dia2[rowIdx - colIdx + n - 1] // 从左往右对角线不在攻击状态
) {
row.push(colIdx); // 将符合的列坐标放入集合内
col[colIdx] = true; // 设置列的攻击范围
dia1[rowIdx + colIdx] = true; // 设置对角线攻击范围
dia2[rowIdx - colIdx + n - 1] = true;
\_helper(rowIdx + 1, row); // 递归找下一行
col[colIdx] = false; // 重置列的攻击范围
dia1[rowIdx + colIdx] = false; // 重置对角线
dia2[rowIdx - colIdx + n - 1] = false;
row.pop(); // 弹出最后的列坐标
}
}
};
const generateBoard = (row) => {
const checkerboard = new Array(n)
.fill()
.map(() => new Array(n).fill(".")); // 生成一个n \* n且都是.的棋盘
for (let i = 0; i < n; i++) {
checkerboard[i][row[i]] = "Q"; // 将对应列设置为Q
checkerboard[i] = checkerboard[i].join(""); // 将这一行转为字符格式
}
return checkerboard;
};
\_helper(0, []); // 从第0行开始放置
return res;
};最后
通过这两章的学习不难发现，回溯算法能解决的问题类型还挺多，以上也只是列举了几个具有代表性的题目。这些题目都有一个共同点就是：需要暴力枚举才能找到所有的解，问题都能被拆解为树型问题。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
