回溯

发表于

# 回溯

解决一个回溯问题，实际上就是一个决策树的遍历过程。我们需要解决三个问题：

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

回溯算法的框架：

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

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

数独问题

大致的代码框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
void solveSudoku(char[][] board) {
    backtrack(board, 0, 0);
}
void backtrack(char[][] board, int r, int c) {
    int m = 9, n = 9;
    for (int i = r; i < m; i++) {
        for (int j = c; j < n; j++) {
            // 做选择
            backtrack(board, i, j);
            // 撤销选择
        }
    }
}
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
// 从1到9做选择，全部试一遍
bool backtrack(char[][] board, int r, int c) {
    int m = 9, n = 9;
    // 当j到达超过最后一个索引时，转为增加i开始穷举下一行
    // 并且在穷举之前添加一个判断，跳过不满足条件的数字
    if (c == n) {
        backtrack(board, r + 1, 0);
        return;
    }
    if (r == m) { // 找到一个可行解，触发base case
        return true;
    }
    // 就是对每个位置进行穷举
    for (int i = r; i < m; i++) {
        for (int j = c; j < n; j++) {
            // 如果该位置是预设的数字，则不用操作
            if (board[i][j] != '.') {
                backtrack(board, i, j + 1);
                return;
            }
            for (char ch = '1'; ch <= '9'; ch++) {
                // 做选择
                // 如果遇到不合法的数字，就跳过
                if (!isValid(board, i, j, ch)) 
                    continue;
                board[i][j] = ch;
                backtrack(board, i, j + 1);
                board[i][j] = '.';
            }
            // 穷举完1~9，依然没有找到可行解
            return false;
        }
    }
    return false;
}

bool isValid(char[][] board, int r, int c, char n) {
    for (int i = 0; i < 9; i++) {
        // 判断行是否存在重复
        if (board[r][i] == n) return false;
        // 判断列是否存在重复
        if (board[i][c] == n) return false;
        // 判断3x3方框是否存在重复
        if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n) return false;
    }
    return true;
}

求子集问题

方法一，递归结构：

这个解法的时间复杂度很高，为O(N*2^N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<vector<int>> subsets(vector<int>& nums) {
    // base case 返回一个空集
    if (nums.empty()) return {{}};
    // 把最后一个元素拿出来
    int n = nums.back();
    nums.pop_back();
    // 先递归算法前面元素的所有子集
    vector<vector<int>> res = subsets(nums);
    int size = res.size();
    for (int i = 0; i < size; i++) {
        // 然后在之前的结果之上追加
        res.push_back(res[i]);
        res.back().push_back(n);
    }
    return res;
}

方法二，回溯算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
    // 记录走过的路径
    vector<int> track;
    backtrack(nums, 0, track);
    return res;
}
void backtrack(vector<int>& nums, int start, vector<int>& track) {
	res.push_back(track);
    // 注意i从start开始递增
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        backtrack(nums, start + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

可以看到，对res的更新是一个前序遍历，也就是说，res是树上的所有节点。

组合问题

输入两个数字n, k，算法输出[1..n]中k个数字的所有组合。