回溯算法

【回溯算法】在 最优解、排列组合、解空间搜素 中存在典型应用

【动态规划】和【贪心算法】都要求 无后效性，即 子问题的解是当前的最优解，不能回退。当这种要求得不到满足时，一种常用做的做法就是采用【回溯算法】进行求解。

【回溯算法】是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解。当发现已不满足求解条件时，就 回溯 返回，尝试别的路径。
【回溯算法】是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，则退回一步重新选择。

这种走不通就退回再走的算法称为【回溯算法】，而满足回溯条件的某个状态点称为【回溯点】

许多复杂的、规模较大的问题都可以使用回溯算法，它又有 通用解题方法 的美称。

基本思想

在包含问题的所有解空间树中，按照 深度优先搜索的策略，从根节点出发，深度探索解空间树。
当探索到某一结点时，先判断该节点是否包含问题的解，如果包含，则从该节点出发继续探索下去；否则逐层向其祖先节点回溯。
若用回溯算法求问题的所有解时，要回溯到根，且根节点的所有可行的子树都要已被搜索遍历才结束。
若只求任意一个解，只要搜索到问题的一个解就可以结束。

其实【回溯算法】就是对隐式图的深度优先搜索算法

基本步骤

• 针对所给的问题，确定问题的解空间：首先明确问题的解空间，应至少包含问题的一个（最优）解
• 确定节点的扩展搜索规则
• 以 深度优先 的方式搜索解空间，并在搜索过程中使用剪枝函数避免无效搜索。

解决一个回溯问题，实际上就是一个 决策树 的遍历过程

【回溯算法】只需要思考三个问题：

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

代码架构

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

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

核心：在 for 循环里面的递归，在递归调用之前 做选择，在递归调用之后 撤销选择

全排列问题

高中数学里有排列组合的问题，n个不重复的数，全排列共有 n! 个
现有一组不重复的数字如[1, 2, 3]，穷举出所有可能的组合？
通常的做法：
先固定第一位1，第二位可以是2，那么第三位只能是3；第二位是3，那么第三位只能是2；
然后就只能变换第一位为1，然后穷举后两位......

其实这就是【回溯算法】，得到【回溯树】

回溯树

只要从根节点遍历这棵树，记录路径上的数字，其实就是所有的全排列！我们不妨把这棵树称为回溯算法的【决策树】。
为什么说这事决策树呢？因为在每个节点上其实都在做决策。
比如，当前站在下图的红色节点上

决策节点

现在就是在做决策：可以选择标记为 [1] 的树枝，也可以选择标记为 [3] 的树枝。为什么只能在[1, 3]之中做选择呢？因为 [2] 树枝在红色节点背后，这个选择已经做过了，而全排列是不允许重复使用数字的。

由此可得：

• [2]就是 路径，记录已经做过的选择
• [1, 3] 就是 选择列表，表示当前可以做出的选择（决策）
• 结束条件 就是遍历到叶子节点，这里的 选择列表 为空

可以把 路径 和 选择列表 作为决策树上每个节点的属性，比如下图列出的节点属性

节点属性

前面定义的 backtrack 函数就像一个指针，在决策树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其 路径 就是一个全排列。

这就涉及到【树的遍历】
多叉树的前序遍历（根->左->右）与后序遍历（左->右->根）

void traverse(TreeNode root) {
    for(TreeNode child: root.children) {
        //... 前序遍历需要的操作
        traverse(child)
        //... 后序遍历需要的操作
    }
}

【前序遍历】的处理是在进入某个节点之前的时间点执行，【后序遍历】的处理在离开某个节点之后的时间点处理。

【路径】和【选择列表】是每个节点的属性函数在树上游走要正确维护节点的属性，那么就要在两个时间点上做处理：

处理时间点

重新理解【回溯算法】的核心框架：

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

即：只要在递归之前做出选择，在递归之后撤销刚做的选择，就能正确得到每个节点的【选择列表】和【路径】。

// 统计排列的链表
List<List<Integer>> res = new LinkedList<>();

/* 主函数 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 中的元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        // 加入统计的链表中
        res.add(new LinkedList(track));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

注：这里并没有显式记录【选择列表】，而是通过nums和track推导出当前的【选择列表】，即：nums中不存在于track里的元素。

当然，这个算法解决全排列问题不是很高效，因为对链表使用 contains() 方法的时间复杂度为O(N)，可以通过 交换元素 优化。但是，不管怎么优化，都符合【回溯框架】，而且时间复杂度都不可能低于O(N!)，因为穷举整颗决策树是无法避免的，这也正是【回溯算法】的特点。不像【动态规划】存在重叠子问题可以优化，【回溯算法】就是纯暴力穷举，复杂度一般都比较高。

全排列 - 交换法

function backtrack(arr, k, result) {
    if(k === arr.length) {
        // 触发结束条件,加入统计列表
        result.push(arr.join('-'))
    }
    // 核心: 以 k 为起点, 依次与后面的元素交换, 产生新的组合
    for(let i = k; i < arr.length; i++) {
        // 做选择：交换 k 与 i 的元素
        swap(arr, i, k)
        // 交换完成后, 继续交换下一个元素, 直至 k == arr.length
        backtrack(arr, k+1, result)
        // 撤销选择：回溯到上一个状态，把两个元素交换回来
        swap(arr, k, i)
    }
}
function swap(arr, i, j) {
    if(i == j) return
    let tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
}

进阶版 - 含有重复元素

考虑到重复元素，一定要优先 排序，将重复的元素放在一起，以便找到重复元素和剪枝。

重复元素的剪枝

由图可知，在第一次使用重复元素时，得到的排列组合是没有问题的。只有在重复使用元素时，才会出现重复的组合。

• 第一次使用元素时，并不需要考虑是否重复，即 重复元素一定会使用一次。
  -- 使用一个变量记录元素是否使用过
• 再次使用一个元素时，发现与前一个元素重复，则剪枝。
  -- 当 arrs[i] == arr[i-1] 时，表示重复使用一个元素（隐含 i > 0）

function backtrack(arr, k, used, result) {
    if(k === arr.length) {
        // 触发结束条件,加入统计列表
        result.push([...arr])
    }
    // 核心: 以 k 为起点, 依次与后面的元素交换, 产生新的组合
    for(let i = k; i < arr.length; i++) {
        // 过滤重复元素，不生成重复组合
        if(i > 0 && arr[i] == arr[i-1] && !used[i-1]) {
            // 第i个元素与第[i-1]个元素相等
            // 且当前并不是在使用第[i-1]个元素, 即第[i-1]个元素已经使用过了
            // 如果继续使用第i个元素，那么产生的组合将重复，故而过滤
            continue
        }
        // 变换状态: 当前正在使用第 i 个元素
        used[i] = true
        swap(arr, i, k)
        // 递归
        backtrack(arr, k+1, used, result)
        // 回溯到上一个状态: 第 i 个元素使用完毕
        used[i] = false
        swap(arr, k, i)
    }
}

let arr = [1, 1, 3], used = [], result
backtrack(arr, 0, used, result)
// result = [[1, 1, 3], [1, 3, 1], [3, 1, 1]]

N 皇后问题

很经典的一个问题：一个 N×N 的国际棋盘，放置 N 个皇后，使得它们不能互相攻击，问有多少种摆法？
注：皇后可以攻击同一行、同一列、左上左下右上右下（同斜线）的任意单位。

棋盘上的皇后

N皇后问题由8皇后问题演变而来，是由国际西洋棋棋手马克思·贝瑟尔于1848年提出：在 8 x 8 格的国际棋盘上摆放 8 个皇后，使其不能相互攻击，即 任意两个皇后都不能处在同一行、同一列、同一斜线上，问有多少种摆法？高斯认为有76种方案，1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

N皇后问题是【回溯算法】的经典案例，有递归版和非递归版。除了递归算法，还有一种【位运算】