回溯-backtracking

1 简介

回溯是一种算法思想，通常借助递归实现，核心就是记录相应的状态值，以降低"试错成本"。

比如，在走迷宫时，我们记录每个叉路口的状态，当遍历完一个叉路口时，如果它的后续路线都是死胡同，那么可以直接回退到上一个还没有遍历完的叉路口，而不用从头开始。

跟DFS的关系？
DFS是针对图形搜索的一种算法实现，通常里面都用到了回溯的思想。而可以用回溯解决的问题，经常也可以抽象出来一个"树形结构"（树也是图的一种）。

应用场景：
如果一个问题，理论上可以通过暴力搜索解决，但是在暴力搜索的过程中会有很多重复操作，这时候可以优化的选择通常有两个，动态规划或者回溯，这两者本质上都是"空间换时间"，通过记录相应的状态值来节省操作时间，动态规划通常能降低一个数量级的时间复杂度，而回溯则是节省了被剪枝优化掉的操作的时间。用回溯解决的问题通常N值都不会太大(小于10)。

2 基本要素

通常应用回溯的时候会借助递归函数，函数中应该包含下面几个要素：

递归结束条件：一般在这里直接输出满足条件的结果，放在函数的最上面
剪枝操作（递归中断条件）：使其区别于暴力搜索的重要因素，理论上，没有剪枝操作的话，回溯跟暴力搜索的时间复杂度是一样的，还要多出递归中栈的空间开销。
中间状态的记录和恢复：在递归调用之前，应该记录结果的中间状态，在递归调用后恢复到这个状态。这里的中间状态指的是获取结果之前，在调用过程中生成的值，比如全排列问题中的未达到指定长度的字符串。
递归调用的参数，通常包含以下几个：
- 源头参数N（用来遍历生成结果的参数N，比如全排列中的字符串）
- 当前的结果的中间状态
- 跟中间状态对应的遍历下标i,表示当前循环正在处理的位置
- 跟N对应的boolean数组，判断对应下标元素是否被遍历过，这个数组在生成第一个元素前要重置（比如全排列9个字符，那么要主方法中要调用递归函数遍历9次，每次遍历都先重置这个数组)
- 保存结果的列表，递归中符合条件的结果直接添加到这个列表中

3 示例–N皇后问题

问题描述：
把N个皇后放在NxN的棋盘上，使其不能互相攻击（不在同一列，不在同一行，不在同一条斜线），给出所有符合条件的放置方法。经典的八皇后问题就是N=8的情况。

这里的数组的表示等按Leetcode51题。

按照上面提到的要素，我们先理一下思路：
首先，每行和每列都只有一个皇后，这一点很容易保证。开始时我们在第一行中的不同位置尝试放置元素，后面的第2行。。。第n行也是如此，它们会判断当前列是否已经存在元素，是的话就返回，尝试下一列。这里的判断还要加上对角线，不难发现，是否在同一对角线可以用两点的横坐标差值是否和纵坐标差值相等（绝对值相等）来判断。

这个问题本质上跟N个字符的全排列类似，只是把N个字符分散在N个字符串中，然后多了一个对角线判断

根据上面的分析，我们先确定以下几个变量：

记录棋盘中对应列是否已经放置了皇后：boolean[N] isColUsed
结果的中间变量：List<String> mid，因为这里用String来表示一行
保存结果的变量:List<List<String>> res

题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<String> mid = new ArrayList<>(); // 用于保存一个“棋谱”
        for (int i = 0; i < n; i++) {
            mid.clear(); // 重置棋谱
            boolean[] isColUsed = new boolean[n]; // 初始化列的使用状态，表示对应的列是否已经被使用
            isColUsed[i] = true; // 下标i的列标记为已使用
            // 先添加每一行，并把每一行的下标i处的字符换为'Q'
            mid.add(new StringBuilder(".".repeat(n - 1)).replace(i, i, "Q").toString());
            backtrack(n, mid, isColUsed, res);
        }
        return res;
    }

    // 这里只传递mid，而没有传递当前处理的行的下标row，因为是从上往下遍历，我们所在的行row=mid.size()
    // 比如mid中保存01234这5行已经处理过的信息，那么说明我们正在处理下标为5的行（第6行）
    public void backtrack(int n, List<String> mid, boolean[] isColUsed, List<List<String>> res) {
        // 递归结束条件，表示我们已经遍历完所有行，注意n是一个越界的下标，如果这里不中止就出错了
        if (mid.size() == n) {
            res.add(List.copyOf(mid)); // 这里必须用copyOf，直接添加mid的话，后续对mid的修改会影响res中的值
            return;
        }

        // 剪枝，递归中断条件
        outerloop:
        for (int j = 0; j < n; j++) {
            // 如果当前列已经被使用，则跳过循环
            if (isColUsed[j] == true) continue;

            // 遍历mid中已经存在的String，得到'Q'的位置，确保后面添加的元素跟其不在一条对角线
            // 这个循环只是一个递归中断条件判断
            for (int i = 0; i < mid.size(); i++) {
                int pos = mid.get(i).indexOf('Q');
                // 判断是否在同一斜线，通过横向和竖向的坐标的差值的绝对值是否相等来判断
                if (Math.abs(mid.size() - i) == Math.abs(pos - j)) continue outerloop;
            }

            // 能到这一步说明当前的列j是符合要求的，记录下这个状态(也就是包含列j的“半个棋谱”），等后面的递归调用处理完以后，删除列j，进入j+1循环（如果j+1列也符合要求，则也会来到这一步）
            // 这里用的是ArrayList,只需要移除最后一个元素即可恢复到上一个状态，所以不用另外记录
            mid.add(new StringBuilder(".".repeat(n - 1)).replace(j, j, "Q").toString());
            // 记录递归前状态
            isColUsed[j] = true;

            // 调用递归，把过程棋谱和列的使用状态都传进去，这步调用的作用就是：
            // 在当前这个符合要求的棋谱状态的基础上，去把剩下的棋谱补全(所有符合要求的棋谱会在最里面这层循环调用时被添加到结果中，也就是前面的递归结束条件)
            backtrack(n, mid, isColUsed, res);

            // 恢复递归前的状态
            isColUsed[j] = false; // 回退，取消该列的占位

            // 回退，移除最后一个元素，恢复到之前那个符合状态的棋谱状态
            // 这一步结束循环，说明包含当前层的列j的棋谱为基础的所有可能性都被遍历过，下一次就尝试当前层的列j+1
            mid.remove(mid.size() - 1); 
        }
    }
}

文章目录

1 简介

2 基本要素

3 示例–N皇后问题