力扣刷题框架——回溯法_力扣 回溯法

原文链接：https://labuladong.gitee.io/algo/1/4/

这篇来讲讲回溯法，其实就是DFS(深度优先搜索)解决一个回溯问题，实际上就是一个决策树的遍历过程。考虑三个问题：

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

代码框架：

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
14
15

1. 全排列问题

这次讨论的全排列问题不包含重复的数字。

1.1 题目描述

给定一个不含重复数字的数组 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 解题思路

暴力穷举，画出决策数：

只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。当你站在2这个节点上，[1,3]就是你的选择列表，表示当前可以做出的选择；结束条件就是遍历到树的底层，在这里就是选择列表为空的时候。我们可以把路径和选择列表作为节点属性

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

多叉树遍历框架

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

代码

public class permuteString {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<Integer>();
        backtrack(nums,track);
        return res;
    }
    public void backtrack(int[] nums,LinkedList<Integer> track){
        //结束条件,如果路径长度等于数组长度说明排列完成
        if(track.size()==nums.length){
            res.add(new LinkedList<Integer>(track));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //做选择，从选择区间选一个加到路径，选择区间是通过track和nums排除出来的
            if (!track.contains(nums[i])){
                track.add(nums[i]);
            }
            else
                continue;
            //进入下一层决策树
            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

2. N皇后问题

2.1 题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。PS：皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

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

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

输入
n = 4

输出
[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]]

解释
如图所示，4 皇后问题存在两个不同的解法。

2.2 解题思路

决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
直接套框架：路径：permute中小于 row 的那些行都已经成功放置了皇后；选择列表：第 row 行的所有列都是放置皇后的选择；结束条件：row 超过 permute 的最后一行。

public class nQueen {
    List<List<String>> res = new ArrayList<List<String>>();
    int n = 0;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        LinkedList<String> permute = new LinkedList<String>();
        StringBuffer line = new StringBuffer();
        //棋盘初始化
        for (int i = 0;i<n;i++){
            line.append('.');
        }
        for (int i = 0;i<n;i++){
            permute.add(line.toString());
        }
        backtrack(permute,0);
        return res;


    }
    public void backtrack(LinkedList<String> permute,int row) {
        if (row == n) {
            res.add(new LinkedList<String>(permute));
            return;
        }
        for (int col = 0; col < n; col++) {
            //做选择,查看这层决策树中各个位置可不可以放
            if(!isValid(permute,row,col))
                continue;
            StringBuffer temp = new StringBuffer(permute.get(row));
            temp.setCharAt(col,'Q');
            permute.set(row,temp.toString());
            backtrack(permute,row+1);
            //撤销选择
            temp.setCharAt(col,'.');
            permute.set(row,temp.toString());




        }
    }
    public boolean isValid(LinkedList<String> permute, int row, int col){
        //检查列是否冲突
        for(int i = 0;i < n;i++){
            String rowstr = permute.get(i);
            if(rowstr.charAt(col) ==  'Q')
                return false;

        }
        //检查左上是否冲突
        for(int i=row-1,j = col-1;i>=0&&j>=0;i--,j--){
            String rowleftstr = permute.get(i);
            if(rowleftstr.charAt(j)=='Q')
                return false;

        }
        //检查右上
        for(int i=row-1,j = col+1;i>=0&&j<n;i--,j++){
            String rowrightstr = permute.get(i);
            if(rowrightstr.charAt(j)=='Q')
                return false;

        }
        return true;
    }

    public static void main(String[] args) {
        int n = 4;
        nQueen nq = new nQueen();
        nq.solveNQueens(n);
    }
}
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
71
72