算法笔记之回溯算法 | Build Knowledge Together

回溯算法 (Backtracking) 是一种经典的算法，它通过对树形或者图形结构执行一次深度优先遍历，实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。实际上，回溯算法就是暴力搜索算法，它是早期的人工智能里使用的算法，借助计算机强大的计算能力帮助我们找到问题的解。

0. 代码结构

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。

上面为回溯算法的一般框架，其本质还是一个for循环，通过不断的“选择”与“撤销”，迭代自身直至达到某个特定的终点。下面为两个例子。

1. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例
输入：[1, 2, 3]
输出：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

如果要手动进行排列组合上面的例子，我们一般会进行这样的操作：先选出数字1，再依次选择2和3、3和2，当1开头的数排列完毕后重新选择2为开头，再类似的操作。对应地，每次所选择的数字为路径，待选择的数字为选择列表，当数字全部选择完后即为结束条件。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {

    var backtrack = (depth = 0) => {

        if (depth === n) {
            res.push(nums.slice())
        }

        for (let i = depth; i < n; i++) {
            [nums[i], nums[depth]] = [nums[depth], nums[i]];
            backtrack(depth + 1);
            [nums[i], nums[depth]] = [nums[depth], nums[i]];
        }

    }

    var n = nums.length
    var res = []
    backtrack()
    return res
};

其中[nums[i], nums[depth]] = [nums[depth], nums[i]];作用为将第depth个数字依次与第i个数字进行交换($i\in[depth, n]$)，即将第i个数字作为第depth层的选择。最后再将交换撤消失。时间复杂度为$O\left ( n\times n! \right )$，空间复杂度为$O\left ( n\times n! \right )$。

图片来自LeetCode(liweiwei1419)

2. N皇后

说到回溯算法就不得不提经典的“八皇后问题”。

如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。

输入：n = 4

输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {

    var backtrack = (line = 0) => {
        if (line === n) {
            let temp = new Array(n).fill(".").map(elem => new Array(n).fill("."))
            temp.forEach((elem, idx) => elem[queensPos[idx]]="Q")
            temp = temp.map(elem => elem.join(""))
            res.push(temp)
        }

        for (let i = 0; i < n; i++) {
            if (cols.has(i) || 
                diagonal1.has(line + i) || 
                    diagonal2.has(line - i)) {
                continue
            }
            queensPos[line] = i
            cols.add(i)
            diagonal1.add(line + i)
            diagonal2.add(line - i)
            backtrack(line + 1)
            cols.delete(i)
            diagonal1.delete(line + i)
            diagonal2.delete(line - i)
        }
    }

    var res = []
    var queensPos = new Array(n).fill(-1)
    var cols = new Set()
    var diagonal1 = new Set()
    var diagonal2 = new Set()
    backtrack()
    return res
    
};

依次遍历所有组合，如果在某一行没有格子可以放置皇后，则撤销上一步回滚到上一状态。时间复杂度为$O\left ( n! \right )$，空间复杂度为$O\left ( n! \right )$。

0. 代码结构

1. 全排列

2. N皇后

3. 参考文献