回溯算法

回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」

框架

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择  // 其实，就是前序遍历的位置：在进入某一个节点之前执行
        backtrack(路径, 选择列表)
        撤销选择 // 后序遍历的位置，在离开某个节点之后执行

注意 Java 的语言特性，因为 Java 函数参数传的是对象引用，所以向 res 中添加 path 时需要拷贝一个新的列表，否则最终 res 中的列表都是空的

在递归之前做选择，在递归之后撤销选择

站在回溯树的一个节点上，你只需要思考 3 个问题：

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

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

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

例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
class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> path=new LinkedList<Integer>();
        boolean[] used=new boolean[nums.length];
        backtrack(nums,path,used);
        return res;
    }
    // 路径：结果保存在path中
    // 选择列表 used数组中为false的
    // 结束条件 used全部为true
    void backtrack(int nums[],LinkedList<Integer> path,boolean[] used){
        if(path.size()==nums.length){  //结束条件
            res.add(new LinkedList<Integer>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!used[i]){  //遍历选择
                //做选择
                path.add(nums[i]);
                used[i]=true;
                backtrack(nums,path,used);
                // 撤销选择
                path.removeLast();
                used[i]=false;
            }
            
        }
    }
}

例2：力扣第 51 题「 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
class Solution {
    List<List<String>> res=new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
       char board[][]=new char[n][n];
       for(int i=0;i<n;i++){
           Arrays.fill(board[i],'.');
       }
        backtrack(board,0);
        return res;
    }
    void backtrack(char[][] board,int row){
        if(row==board.length){ //结束条件
            print(board);
            return;
        }
        for(int col=0;col<board.length;col++){
            if(isValid(board,row,col)){  //满足条件，做选择
                board[row][col]='Q';
                backtrack(board,row+1);
                //撤销选择
                board[row][col]='.';
            }
        }
    }

    // 判断是否可以在board[row][col] 放置皇后
    boolean isValid(char[][] board,int row,int col){
        int n=board.length;
        for(int i=0;i<row;i++){
            if(board[i][col]=='Q'){
                return false;
            }
        }
         // 判断左斜线上是否有皇后
        for(int i=1;i<=Math.min(row,col);i++){
            if(board[row-i][col-i]=='Q'){
                return false;
            }
        }
        // 判断右斜线上是否有皇后
        for(int i=1;i<=Math.min(row,n-1-col);i++){
            if(board[row-i][col+i]=='Q'){
                return false;
            }
        }
        return true;
    }
    
    void print(char[][] board){
        LinkedList<String> temp=new LinkedList<String>();
        for(int i=0;i<board.length;i++){
            temp.add(new String(board[i]));
        }
        res.add(temp);
    }
    
}

使用回溯算法解决排列-组合-子集问题

组合树

image-20221013110112647

特性：

将根节点作为第0层，该节点的值为该节点到根节点之间树枝上的元素，第n层的所有节点就是大小为n的所有子集。

子集 不含重复元素

组合

子集 II 含重复元素

跟子集那题的不同之处，在于给出的数组中是含有重复元素的

我一开始想的是，结果集用Set来装不就可以去除重复的吗？ 但不对，在回溯的时候，我们需要将上一次加入的节点移除，那set这个数据结构做不到，它只能将指定的元素移除。

正确做法：剪枝

image-20221014090918402

先将元素排序，如果nums[i]==nums[i-1]跳过

image-20221013110126245

组合总和 II

全排列 II 含重复元素

如何将去掉重复的排列 –>如何剪枝

【保证相同元素在结果中的相对位置保持不变】

组合总和 元素无重，可重复选

image-20221014105002963

集合划分

把装有n个数字的数组nums分成k个和相同的集合

从数字的角度

每个数字都要放入k个桶中的一个 【有些可以放，有些不可以】

从桶的角度

对于每个桶，遍历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
class Solution {
    int bucket[];
    public boolean canPartitionKSubsets(int[] nums, int k) {
        bucket = new int[k];
        int sum = 0;
        for (int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum % k !=0){
            return false;
        }
        int target=sum/k;
        Arrays.sort(nums);
        boolean vis[]=new boolean[nums.length];
        return backtrack(nums,0,target,vis);
    }
    // 思路1：nums数组的每一个数字放到bucket   超时
    // 思路2: 从桶的视角，对于每一个桶，遍历nums数组中的每个数字，看是否放入这个桶
    boolean backtrack(int nums[],int index,int target,boolean vis[]){
        if(index==bucket.length){ //终止条件
            for(int i=0;i<nums.length;i++){
                if(!vis[i]){
                    return false;
                }
            }
            return true;
        }
        // 列举所有选择，每个球只能放入一个桶
        for(int i=0;i<nums.length;i++){
            // 减枝
            if(vis[i]){
                continue;
            }
            if(bucket[index]+nums[i]>target){
                continue;
            }
            //做选择
            bucket[index]+=nums[i];
            vis[i]=true;
            if(bucket[index]==target){
                if(backtrack(nums,index+1,target,vis)){
                    return true;
                }
            }else{  //未装满，继续装
                continue;
            }
            
            //撤销选择
            bucket[index] = bucket[index]-nums[i];
            vis[i]=false;
        }
        // 没有任何一个数字可以放入这个桶
        return false;
    }
}

两种方式都有超时，还没优化

BFS算法

BFS问题的本质就是从一幅图的起点到终点的最短距离

框架：

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
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

打开转盘锁

双向BFS优化

传统的BFS：从起点开始到四周扩散，遇到终点时停止。

双向BFS:从起点和终点同时扩散，当两边有交集时停止。