回溯算法模板

回溯算法模板

回溯问题：一个决策树的遍历问题。

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

经典问题：“全排列”、“N皇后问题”。

回溯算法框架：

result = []
def backtrack(路径,选择列表):
    if 满足结束条件:
    	result.add(路径)
    	return
    for 选择 in 选择列表:
    	# 做选择
    	将该选择从选择列表中移除
    	路径.add(选择)
    	backtrack(路径,选择列表)
    	# 撤销选择
    	路径.remove(选择)
    	将该选择恢复到选择列表
1
2
3
4
5
6
7
8
9
10
11
12
13

注意：写backtrack函数时，需要维护走过的“路径”和当前可以做的“选择列表”，当触发“结束条件”时，将“路径”记入结果集。

经典案例

1.全排列问题

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

全排列代码如下：

private List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它的全排列 */
public 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();
    }
}
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

2.N皇后问题

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

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

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

示例 1：

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

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

代码如下：

class Solution {
    List<List<String>> res = new ArrayList<>();
    char[][] board;
    int n;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        board = new char[n][n];
        // 全部置为'.'
        for (char[] chs : board) Arrays.fill(chs, '.');
        dfs(0);
        return res;
    }

    // 以每一行为dfs变量
    private void dfs(int r) {
        // r到达n,说明[0,n-1]行已经填满皇后了
        if (r == n) {
            List<String> list = new ArrayList<>();
            for (char[] chs : board) list.add(new String(chs));
            res.add(list);
        }
        // 考虑[r,c]
        for (int c = 0; c < n; c++) {
            // 格子无效直接跳过
            if (!isValid(r, c)) continue;
            // 有效就添加皇后
            board[r][c] = 'Q';
            // 这行摆了一个就不能再白,继续看下一行
            dfs(r + 1);
            // 撤回
            board[r][c] = '.';
        }
    }

    // 判断当前位置是否能放下皇后(只考虑目前已经放下的)
    private boolean isValid(int r, int c) {
        // 排除法:这里不用考虑行是否存在Q,因为dfs逻辑决定同一条路径同一行只会放一位皇后
        // 考虑同一列[0,r-1]
        for (int i = 0; i < r; i++) {
            if(board[i][c] == 'Q') return false;
        }
        // 考虑两条斜边:左上->右下+右上+左下
        for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
            if(board[i][j] == 'Q') return false;
        }
        for (int i = r - 1, j = c + 1; i >= 0 && j <= n - 1; i--, j++) {
            if(board[i][j] == 'Q') return false;
        }
        // 排出后就是true
        return true;
    }
}
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