回溯算法

发表于 分类于 ， 阅读次数： Waline： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

我们先理解几个问题：

1，回溯算法是什么？解决回溯算法相关的问题有什么技巧？如何学习回溯算法？回溯算法代码有什么规律？

回溯算法其实就是DFS算法，本质上就是一种暴力穷举算法。

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

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

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

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

回溯算法框架：

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

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

46. 全排列

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

示例：

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

思路：

我们把这棵树称为回溯算法的「决策树」。因为我们在每个节点上都是在做决策。

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
class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int> > permute(vector<int>& nums) {
        //记录路径
        vector<int> track;
        //标记数组，避免重复使用
        vector<bool> used(nums.size());

        backtrack(nums, track, used);
        return res;
    }
    void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used){
        //结束条件：nums 中的元素全部在 track 中
        if(track.size() == nums.size()){
            res.push_back(track);
            return;
        }

        for(int i = 0; i < nums.size(); i++){
            //排除不合法的选择
            if(used[i]){
                //num[i] 已经在 track 中，跳过
                continue;
            }
            //做选择
            track.push_back(nums[i]);
            used[i] = true;
            //进入下一层决策树
            backtrack(nums, track, used);
            //取消选择
            track.pop_back();
            used[i] = false;
        }
    }
};

51. N 皇后

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

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

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

每一行每一列每一条直线只有一个皇后

示例：

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

思路：

路径：board 中小于 row 的那些行都已经成功放置了皇后

选择列表：第 row 行的所有列都是放置皇后的选择

结束条件：row 超过 board 的最后一行

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
class Solution {
public:
    vector<vector<string> >res;
    vector<vector<string> > solveNQueens(int n) {
        //初识化棋盘：'.'表示空，'Q'表示皇后。
        vector<string> board(n, string(n,'.'));
        backstrack(board, 0);
        return res;
    }
    //路径：board 中小于 row 的那些行都已经成功放置了皇后
    //选择列表：第 row 行的所有列都是放置皇后的选择
    //结束条件：row 超过 board 的最后一行
    void backstrack(vector<string>& board, int row){
        //终止条件
        if(row == board.size()){
            res.push_back(board);
            return;
        }

        int n = board[row].size();
        for(int col = 0; col < n; col++){
            //排除不合法的选择
            if(!isValid(board, row, col)){
                continue;
            }
            //做选择
            board[row][col] = 'Q';
            //进入下一行决策
            backstrack(board, row + 1);
            //撤销选择
            board[row][col] = '.';
        }
    }
    //是否可以在 board[row][col]放置皇后
    bool isValid(vector<string>& board, int row, int col){
        int n = board.size();
        //检查列是否有皇后互相冲突
        for(int i = 0; i < n; i++){
            if(board[i][col] == 'Q')
                return false;
        }
        //检查右上方是否有皇后互相冲突
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++){
            if(board[i][j] == 'Q')
                return false;
        }
        //检查左上方是否有皇后互相冲突
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--){
            if(board[i][j] == 'Q')
                return false;
        }
        return true;
    }
};