回溯算法解题套路示例

发表于 分类于

回溯算法和我们常说的 DFS 算法非常类似，本质上就是一种暴力穷举算法。回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」。

直接上回溯算法框架，解决一个回溯问题，实际上就是一个决策树的遍历过程，站在回溯树的一个节点上，你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法伪代码套路：

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。

下面通过全排列问题和N皇后问题展开进行理解。

全排列问题

题面描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

题目分析

我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个。那么我们当时是怎么穷举全排列的呢？

比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：

先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……

其实这就是回溯算法，如下这棵回溯树：

img

只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。

为啥说这是决策树呢，因为你在每个节点上其实都在做决策。

比如现在到了第二层的节点2，你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层叶子节点，这里也就是选择列表为空的时候。

如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性，比如下图列出了几个蓝色节点的属性：

img

我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层叶子节点，其「路径」就是一个全排列。

再进一步，如何遍历一棵树？

1
2
3
4
5
6
7
void traverse(TreeNode root) {
    for (TreeNode child : root.childern) {
        // 前序位置需要的操作
        traverse(child);
        // 后序位置需要的操作
    }
}

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

下面，直接看全排列代码：

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
private List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    LinkedList<Integer> track = new LinkedList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, track, used);
    return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
    if(track.size() == nums.length){
        res.add(new LinkedList<>(track));
        return;
    }
    for(int i=0;i<nums.length;i++){
        //排除不合法的选择，nums[i]已经在track中，跳过
        if(used[i])
            continue;
        //做选择
        track.add(nums[i]);
        used[i] = true;
        //进入下一层决策树
        backtrack(nums, track, used);
        //取消选择
        track.removeLast();
        used[i] = false;
    }
}

N皇后问题

题面描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

img

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：
输入：n = 1
输出：[[“Q”]]

提示：
1 <= n <= 9

题目分析

这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

直接先上代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
private List<List<String>> resQueens;
public List<List<String>> solveNQueens(int n) {
    resQueens = new ArrayList<>();
    final int N = n;
    // '.' 表示空，'Q' 表示皇后，初始化空棋盘
    final StringBuilder sb = new StringBuilder();
    for(int i=0;i<n;i++){
        sb.append(".");
    }
    final List<String> board = new ArrayList<String>(){
        {
            for(int i=0;i<N;i++){
                add(sb.toString());
            }
        }
    };
    backTrackQueens(board, 0);
    return resQueens;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backTrackQueens(List<String> board, int row){
    //触发结束条件
    if(board.size() == row){
        resQueens.add(new ArrayList<>(board));
        return;
    }
    int n = board.get(row).length();
    for(int col=0;col<n;col++){
        //排除不合法的选项
        if(!isValid(board, row, col))
            continue;
        String rowStr = board.get(row);
        //做选择
        board.set(row, setIndexChar(rowStr, col, 'Q'));
        //进入下一行决策
        backTrackQueens(board, row + 1);
        //撤销选择
        board.set(row, setIndexChar(rowStr, col, '.'));
    }
}
/* 是否可以在 board[row][col] 放置皇后？ */
private boolean isValid(List<String> board, int row, int column){
    int n = board.size();
    //同一列检测
    for(int i=0;i<n;i++){
        if('Q'==(board.get(i).charAt(column))){
            return false;
        }
    }
    //左上检测
    for(int i=row-1, j=column-1;i>=0&&j>=0;i--,j--){
        if('Q'==(board.get(i).charAt(j))){
            return false;
        }
    }
    //右上检测
    for(int i=row-1, j=column+1;i>=0&&j<n;i--,j++){
        if('Q'==(board.get(i).charAt(j))){
            return false;
        }
    }
    return true;
}
private String setIndexChar(String rowStr, int index, char c){
    char[] chars = rowStr.toCharArray();
    chars[index] = c;
    return new String(chars);
}

函数 backtrack 依然像个在决策树上游走的指针，通过 row 和 col 就可以表示函数遍历到的位置，通过 isValid 函数可以将不符合条件的情况剪枝：

N 行棋盘中，第一行有 N 个位置可能可以放皇后，第二行有 N - 1 个位置，第三行有 N - 2 个位置，以此类推，再叠加每次放皇后之前 isValid 函数所需的 O(N) 复杂度，所以总的时间复杂度上界是 O(N! * N)，而且没有什么明显的冗余计算可以优化效率。你可以试试 N = 10 的时候，计算就已经很耗时了。

当然，因为有 isValid 函数剪枝，并不会真的在每个位置都尝试放皇后，所以实际的执行效率会高一些。但是这个时间复杂度作为上界是没问题的。