文章

Refresh - 回溯

发表于
作者 puppylpg 52 分钟阅读

关于普通回溯、树的dfs（和bfs）、图的dfs。

  1. 回溯DFS
    1. 退回来怎么退？恢复现场！
    2. 回溯一种情况之后该做什么
    3. dfs模板
      1. dfs参数列表
      2. 用模板去写
    4. 再说剪枝
    5. 题目类型：子集
  2. 从图的角度再理解DFS和BFS
    1. DFS与网格
    2. BFS与网格 - 层序遍历/最短路径
      1. bfs与Dijkstra
  3. DFS总结

回溯DFS

回溯其实就是dfs。

比如括号生成和电话号码的字母组合，其思路就是：

  1. 当前情况和接下来的a去组合；
  2. 退回来，当前情况和接下来的b去组合；
  3. 退回来，……
  4. 每一种情况的结束条件：字符够长了，到底了；

仔细想想，他们的本质就是在构建N叉树。因此对每种情况是否还要继续递归进去所做的条件判断，就等于是在给树剪枝。

而括号生成的这个答案说的特别好——无论我们选择深度优先还是广度优先，无非是在考虑如何去遍历这棵树！

  1. 深度优先（回溯）就是在使用系统栈的深度做优先遍历（所以我们看它的空间复杂度分析，如果每层都是O(1)，那空间复杂度就是栈的层数O(k)）；
  2. 我们也可以自己使用栈编写深度优先遍历（这时候空间复杂度就很明显了，就是我们所用的栈O(k)）；
  3. 而广度优先遍历，其实是程序猿自己编写节点类，使用队列存储这个数据结构；

因此核心在于心中要有那棵树！

关于剪枝：如果不让结果有重复值，那么一般需要先排个序，然后考虑相同元素直接跳过！关于重复元素的过滤，提前剪枝比在最后结果里去重要好得多！因为少了无数的递归运算！比如组合总和 II，如果不剪枝而是想生成所有结果之后再去做去重处理，会被这个用例卡超时：

1
2

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
30

注意：“提前剪枝”的“提前”指的是“不要让某些显然已经不符合条件的分支一直递归下去”，至于是进入下一个dfs函数之后剪（采用return），还是在进入下一个dfs函数之前剪（采用if语句跳过），没什么区别，前者只是比后者多进入了一层函数，但都属于“提前”剪枝。

相关题目：

系列：

回溯的题型列表可以参考这里的整理。

退回来怎么退？恢复现场！

回退的时候，其实就是要恢复上一次试探前的现场。

比如常见的生成字符串，“现场”就是当前已经记录的字符集合，那么就要看字符是append到当前集合还是重新new了一个新集合：

  1. 进入下一层的时候，如果没有污染当前字符集合（new），则方法返回的时候已经是回退了；
  2. 进入下一层的时候，如果当前集合被污染了（append），则方法返回后要把当前数据修改为原样，一般是一个delete操作；

第一种情况比如括号生成：这种写法里，传参用的是新string，不影响当前string；如果用StringBuilder，就会影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // dfs真好用……
        // 剪枝，第一个一定是(
        dfs(result, "(", n, 1, 0);
        return result;
    }

    private void dfs(List<String> result, String curString, int n, int left, int right) {
        // 剪枝，最后一个一定是)
        if (curString.length() == n * 2 - 1) {
            result.add(curString + ')');
        } else {
            // 剪枝，中间如果已经不满足了，就别搞了
            if (left < n) {
                dfs(result, curString + '(', n, left + 1, right);
            }
            if (right < left && right < n - 1) {
                dfs(result, curString + ')', n, left, right + 1);
            }
        }
    }

第二种情况比如电话号码的字母组合：这种写法没有用新string，而是用了StringBuilder，就影响了当前StringBuilder的值。

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

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

使用string的时候，更简洁：

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 {

    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if (digits.length() == 0) {
            return result;
        }

        dfs(result, 0, "", digits);
        return result;
    }

    private void dfs(List<String> result, int step, String buffer, String digits) {
        if (digits.length() == step) {
            result.add(buffer);
            return;
        }

        String conditions = phoneMap.get(digits.charAt(step));
        for (int i = 0; i < conditions.length(); i++) {
            dfs(result, step + 1, buffer + conditions.charAt(i), digits);
        }
    }
}

对于其他情况，原则是一样的，“恢复现场”，但是实践起来会有所区别。

比如不同路径 III，只有在当前格子探索完了之后（从当前格子的上下左右方向都试探了），返回上级之前，才需要恢复现场，所以return之前要reset：

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

class Solution {
    public int uniquePathsIII(int[][] grid) {
        int row = grid.length, col = grid[0].length;

        int length = 0, si = -1, sj = -1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    length++;
                }

                if (grid[i][j] == 1) {
                    si = i;
                    sj = j;
                }
            }
        }

        // 要经过length个0，那么需要length+1步才能到达重点
        return dfs(grid, length + 1, 0, si, sj);
    }

    // step: cur step number
    private int dfs(int[][] grid, int length, int step, int i, int j) {
        // border
        if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0) {
            return 0;
        }

        // result
        if (step == length) {
            return grid[i][j] == 2 ? 1 : 0;
        }

        // obstacle
        if (grid[i][j] == -1 || grid[i][j] == 2) {
            return 0;
        }

        // already walked
        if (grid[i][j] > 10) {
            return 0;
        }

        // mark
        grid[i][j] += 20;

        int a = dfs(grid, length, step + 1, i + 1, j);
        // reset(grid, i + 1, j);
        int b = dfs(grid, length, step + 1, i, j + 1);
        // reset(grid, i, j + 1);
        int c = dfs(grid, length, step + 1, i - 1, j);
        // reset(grid, i - 1, j);
        int d = dfs(grid, length, step + 1, i, j - 1);
        // reset(grid, i, j - 1);
        
        // 只有上下左右都探索完了，才需要回，所以应该在这里reset，而不是每一步之后
        reset(grid, i, j);

        return a + b + c + d;
    }

    private void reset(int[][]grid, int i, int j) {
        if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0) {
            return;
        }

        if (grid[i][j] > 10) {
            grid[i][j] -= 20;
        }
    }
}

一开始想错在了两个地方，看注释掉的代码就能看出来：

  1. 不用考虑reset下一步里染色过的格子（属于是逻辑混乱了），只需要考虑当前步骤的回退工作，那么下一步回退的时候，自然会reset好它们那层的状态；
  2. 只考虑reset当前格子，就会发现上下左右每次探索前都需要染色当前格子，那么每一次回溯后就不需要动当前格子，只有最后要出这一层的时候，才需要reset。

由于是最后才需要回溯一次，而不是每一次都回溯，所以回溯也不用这么麻烦（+20，判断>+10），只需要一开始记录下当前值，退出前set回去就行了。比如官方答案：

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

class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int uniquePathsIII(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        int si = 0, sj = 0, n = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 0) {
                    n++;
                } else if (grid[i][j] == 1) {
                    n++;
                    si = i;
                    sj = j;
                }
            }
        }
        return dfs(grid, si, sj, n);
    }

    public int dfs(int[][] grid, int i, int j, int n) {
        if (grid[i][j] == 2) {
            return n == 0 ? 1 : 0;
        }
        int r = grid.length, c = grid[0].length;
        int t = grid[i][j];
        grid[i][j] = -1;
        int res = 0;
        for (int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && ni < r && nj >= 0 && nj < c && (grid[ni][nj] == 0 || grid[ni][nj] == 2)) {
                res += dfs(grid, ni, nj, n - 1);
            }
        }
        grid[i][j] = t;
        return res;
    }
}

其实路径总和 II也类似，最后才reset。

和字符串回溯问题相比，不同路径 III很有意思，区别点在于context的有状态性：

  • 字符串回溯，context是字符串，当前层每一种情况回溯过后（恢复完context），字符串也是干净的，最后就可以直接退出了；
  • 这个题，context是原始二维数组，当前层每一种情况回溯过后，最后要来个总的context reset行为，恢复原始二维数组，才能退出；如果每次进入下一层，用的是新new的二维标记数组，就不需要考虑这一步了，但是那样传参的时候就太麻烦了。

和下面岛屿问题的区别在于，岛屿问题只染色，不清除，直接回溯；这个是需要清除标记的，所以是更纯粹的回溯问题。

回溯一种情况之后该做什么

这个很重要！一般一段时间不写回溯后，就会卡在这里！回溯之后干什么？当然是继续枚举其他情况。怎么枚举？

比如上述括号生产，总共就两种情况：

  • 先试左括号
  • 再试右括号

这种情况直接写两个回溯即可。

对于电话号码的字母组合，每一个字母都对应k种情况（k为当前数字对应的字母的个数），这时候就应该用for循环，循环每一种情况去写回溯。

dfs模板

所以回溯问题的模板就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

dfs:
    不符合？（这也是在剪枝，进入下一层dfs后的剪枝）
        return

    终结条件？
        收集结果
        return
        
    如果符合情况（剪枝，进入下一层dfs前的剪枝）：
        获取下一步里所有的情况（k个）
        for i in k：
            dfs（枚举每一种情况）
            回来了：如果污染了，就把数据处理回来，否则for循环里啥也不用写，就可以进行下一种情况了
            
        # 如果context依然不干净（eg：二维数组标记），也可能需要在所有探索分支都reset之后，最后再来个reset行为

建议先写不符合条件时的return，再写满足结果时收集结果的return。

注意：如果k很小，就不要用for了。比如二叉树，或者图遍历，直接枚举2、4种情况就行了！

dfs参数列表

另一个问题就是，dfs函数的参数都应该是什么？这个主要就是看需要什么：

  • list：收集结果
  • step
  • 当前生成中的数据
  • n：最长多少步。因为要知道什么时候终结

其他数据看情况，需要就加进来。

比如上述括号生成，当前有多少个左括号和右括号是需要用到的数据，就放入参数列表直接传进去，免得再统计了。

比如下述路径总和II，当前所有值的sum就是必要信息（当然用减法似乎更好一些，防止溢出的情况），不然每一步里都得算。这样的话sum也应该作为参数。

用模板去写

比如按照模板写上述电话号码字母组合——

  1. dfs参数用了String digits，因为要知道当前这一步的数字，才能找到对应的字母。同时它隐含了n的信息（digits.length()），所以就不用传n了；
  2. 找到对应的字母之后，for循环试探每一种情况就行了；
  3. 因为生成中的数据用的是string而非stringbuilder，所以不会污染当前生成中的数据，回溯后就不用考虑擦除了；
    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 {

 Map<Character, String> phoneMap = new HashMap<Character, String>() {{
     put('2', "abc");
     put('3', "def");
     put('4', "ghi");
     put('5', "jkl");
     put('6', "mno");
     put('7', "pqrs");
     put('8', "tuv");
     put('9', "wxyz");
 }};

 public List<String> letterCombinations(String digits) {
     List<String> result = new ArrayList<>();

     if (digits.length() == 0) {
         return result;
     }

     dfs(result, 0, "", digits);
     return result;
 }

 void dfs(List<String> result, int step, String buffer, String digits) {
     if (digits.length() == step) {
         result.add(buffer);
         return;
     }

     String conditions = phoneMap.get(digits.charAt(step));
     for (int i = 0; i < conditions.length(); i++) {
         dfs(result, step + 1, buffer + conditions.charAt(i), digits);
     }
 }
}

    或者：

    1
2
3
4

             // 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
         if (i > begin && candidates[i] == candidates[i - 1]) {
             continue;
         }

    再说剪枝

    我觉得dfs有三大麻烦的地方：

  4. dfs的模板。没模板是没法写的，但我们已经总结出来了；
  5. dfs方法参数列表：上面总结的几个参数是关键参数，其他看情况决定加不加；
  6. 剪枝：上面两步相对固定，也相对好搞定。最灵活的当属剪枝了，很多时候，一个题能不能过，就看需不需要剪枝，好不好剪枝。
    1. 上述电话号码组合字母，压根不需要剪枝，所有的情况都是符合的，最简单；
    2. 上述括号生成，剪枝的条件稍微麻烦一些：左括号不能多余n，右括号不能多于左括号；

再看组合总和 II，更麻烦！因为结果不能重复，前一个结果里用了那个1，后一个结果里用了这个1，是不行的。如果想逃避剪枝，比如把结果全都收集起来再去重，也是不行的，因为会被一个全是1的用例卡超时，它就是为了让你绕不过剪枝，只能剪枝。

这个时候如果能想到先排个序，然后“同层相同元素”只用一个，就能剪掉不少枝！

同层指：比如1, 2, 2, 2，如果第一个2是上层探索的，那么这一层可以用第二个2；如果这层已经用了2，如果后面还有2，本层不要再用2，否则“本层用第一个2”就和“本层用第二个2”重复了。

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

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 不能包含重复解，但是候选数字本身有重复，所以要排个序，方便跳过
        Arrays.sort(candidates);

        List<List<Integer>> result = new ArrayList<>();
        dfs(result, candidates, target, new ArrayList<>(), 0);
        return result;
    }

    // 传入start，是因为要求结果无重复
    private void dfs(List<List<Integer>> result, int [] candidates, int target, List<Integer> context, int start) {
        if (target == 0) {
            result.add(new ArrayList<>(context));
            return;
        }

        if (target < 0) {
            return;
        }

        // 结果无重复，所以只能一直往后找，因此不能一直从0开始找
        for (int i = start; i < candidates.length; i++) {
            int value = candidates[i];

            // 本层的重复数字不能重复用，不同层的数字可以重复
            // 所以前一个数字必须得在本层（i-1>=start），才去判断当前值是否要跳过
            if (i - 1 >= start && value == candidates[i - 1]) {
                continue;
            }

            context.add(value);
            // 因为数字不可以重复用，所以下一个是从i+1开始探索
            dfs(result, candidates, target - value, context, i + 1);
            context.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
31
32
33
34
35
36
37
38
39
40
41
42

    void dfs(List<List<Integer>> result, int step, int[] candidates, int sum, List<Integer> cur, int target) {
        if (sum > target) {
            return;
        }

        if (sum == target) {
            result.add(new ArrayList<>(cur));
            return;
        }

        for (int i = step; i < candidates.length; i++) {
            int next = candidates[i];

            // 之前有过这个数，当前的候选集里还没用过，咱也别用了：
            // 要么它不符合条件，咱也别忙活了
            // 要么它符合条件，用过了，再要这个就重复了
            boolean skip = false;

            int sameValue = 0;
            for (int j = 0; j < i; j++) {
                if (candidates[j] == next) {
                    sameValue++;
                }
            }

            int using = 0;
            for (Integer integer : cur) {
                if (integer == next) {
                    using++;
                }
            }

            // 比如之前出现过两次，现在已经用了一次了，别再放第二次了，再放也是重复
            if (using < sameValue) {
                continue;
            }

            cur.add(next);
            dfs(result, i + 1, candidates, sum + next, cur, target);
            cur.removeLast();
        }
    }

所以剪枝确实很考验思维。我们也应该记住，修改（比如sort）源数据是个可以考虑的方案。

在括号相关的题目中，左括号要始终>=右括号，否则字符串就不符合要求了。如果一个左括号score+1，一个右括号score-1，那么score要时刻保持大于0，用这一点剪枝非常有效。比如删除无效的括号：

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        // remove Left, remove Right
        int rl = 0, rr = 0, n = s.length();

        int curL = 0, curR = 0, totalL = 0, totalR = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                curL++;
                totalL++;
            }
            if (c == ')') {
                curR++;
                totalR++;
            }

            if (curR > curL) {
                rr++;
                curR--;
            }
        }

        rl = curL - curR;

        // print("rl", rl);print("rr", rr);

        Set<String> result = new HashSet<>();

        dfs(result, "", rl, rr, 0, s, 0);

        return new ArrayList<>(result);
    }

    private void dfs(Set<String> result, String cur, int rl, int rr, int index, String raw, int score) {
        // 剪枝：如果左右已经不对了，没必要继续下去
        if (score < 0) {
            return;
        }

        // print("rl", rl);print("rr", rr);print("index", index);print("cur", cur);print("charAt", raw.charAt(index));
        if (rl == 0 && rr == 0) {
            if (isValid(cur + raw.substring(index))) {
                result.add(cur + raw.substring(index));
                return;
            }
            
            // 在增长的过程中，不必check cur是否有效，还没增加完，很可能是无效的
            // 在rl = rr = 0的时候做校验，这是一种剪枝
            if (!isValid(cur)) {
               return;
            }
        }

        // 这个不算剪枝，已经到头了，只能算最后的无效字符串过滤条件，不如换成下面这个剪枝1
        if (index == raw.length()) {
            return;
        }

        // 剪枝1：如果剩余的字符不够删了，提前结束
        if (rl + rr > raw.length() - index) {
            return;
        }

        if (rl > 0 && raw.charAt(index) == '(') {
            dfs(result, cur, rl - 1, rr, index + 1, raw, score);
        }

        if (rr > 0 && raw.charAt(index) == ')') {
            dfs(result, cur, rl, rr - 1, index + 1, raw, score);
        }

        if (raw.charAt(index) == '(') {
            score++;
        } else if (raw.charAt(index) == ')') {
            score--;
        }
        dfs(result, cur + raw.charAt(index), rl, rr, index + 1, raw, score);

        // 恢复上下文
        if (raw.charAt(index) == '(') {
            score--;
        } else if (raw.charAt(index) == ')') {
            score++;
        }
    }

    private boolean isValid(String s) {
        int curL = 0, curR = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                curL++;
            }
            if (c == ')') {
                curR++;
            }

            if (curR > curL) {
                return false;
            }
        }

        return curL == curR;
    }
}

不剪枝/加上剪枝1/再加上score剪枝，耗时分别为：522/36/13ms。

但是注意这里score=0并不能作为最终字符串是否有效的标志，因为最后一段是直接用substring拼接上去的，没有计算score。score只是标记了当前生成中的字符串是否是合法的。

本题递归空间为2^n（相当于子集判断），生成字符串以后要再叠加isValid判断，所以是O(n * 2^n)。

题目类型：子集

单独子集类型的题目拉出来，是因为发现时隔不久之后，再写回溯的时候就“心中没树”了！所以再拉出来把解题模板强化一遍。

子集这道题的官方解法比较正统一些：每一个位置可以选或不选，就像二叉树一样，所以用两个dfs，结束条件是遍历到了集合的最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, 0, new ArrayList<>(), nums);

        return result;
    }

    private void dfs(List<List<Integer>> result, int i, List<Integer> cur, int[] nums) {
        if (i == nums.length) {
            result.add(new ArrayList<>(cur));
            return;
        }

        int curInteger = nums[i];
        cur.add(curInteger);
        // with cur integer
        dfs(result, i + 1, cur, nums);
        cur.removeLast();

        // without cur integer
        dfs(result, i + 1, cur, nums);
    }
}

关键点还是那句话：心中有树！

而我写了一个很抽象的解法：dfs负责取长度为k的元素集合。由于是子集，所以k可以从0（空集）到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

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i <= n; i++) {
            dfs(result, new ArrayList<>(), 0, nums, i);
        }
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> cur, int start, int[] nums, int k) {
        if (cur.size() == k) {
            result.add(new ArrayList<>(cur));
            return;
        }

        int n = nums.length;
        if (start >= n) {
            return;
        }

        for (int i = start; i < n; i++) {
            int curNum = nums[i];
            cur.add(curNum);
            dfs(result, cur, i + 1, nums, k);
            cur.removeLast();
        }
    }
}

在我的解法里，遍历的时候用了for，代表当前节点可以有[start, n)种选择：

  • 如果使用了当前i，代表不跳过第i个元素；
  • 回溯之后（删掉字符，代表不使用第i个元素），再i++后，就相当于跳过了第i个元素；

这个思路现在来看依然是有点儿抽象的。相当于每一步都在全排列，最终能生成长度为k的子数组就要，否则就当组错了，丢弃。我觉得这是一种for的误用，多回溯了很多种情况，只不过最后使用cur.size() == k把不符合条件的结果都过滤了。

比如继续看字母大小写全排列，如果用类似上述官解的思路就比较简单：字母分为大小写，所以是二叉，数字没有变形，所以是单叉：

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

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        dfs(result, "", 0, s);
        return result;
    }

    private void dfs(List<String> result, String cur, int start, String raw) {
        int n = raw.length();
        if (cur.length() == n) {
            result.add(cur);
            return;
        }

            int i = start;
        // 压根不需要for，因为每一个字符都得用上
        // for (int i = start; i < n; i++) {
            char c = raw.charAt(i);
            if (Character.isDigit(c)) {
                // 这里是单叉数
                dfs(result, cur + c, i + 1, raw);
            } else {
                // 像是一颗二叉树，在这里发生了分叉，每一个分支遍历到
                dfs(result, cur + Character.toLowerCase(c), i + 1, raw);
                dfs(result, cur + Character.toUpperCase(c), i + 1, raw);
            }
        // }
    }
}

也不需要for。虽然最终结果对了，但全靠size == n给过滤的，实际上for i++之后，相当于没使用当前字符，这样最终字符串长度肯定不对，相当于多了很多无效回溯，所以最终代码只击败了5%的人。去掉for后，击败了23%，从99ms降到了7ms，快了非常多。之所以才23%，应该用sb会比用string快，毕竟2^n的复杂度，多生成了很多string对象。

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

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList<>();
        dfs(result, "", 0, s);
        return result;
    }

    private void dfs(List<String> result, String cur, int start, String raw) {
        int n = raw.length();
        if (cur.length() == n) {
            result.add(cur);
            return;
        }

        for (int i = start; i < n; i++) {
            char c = raw.charAt(i);
            if (Character.isDigit(c)) {
                // 这里是单叉数
                dfs(result, cur + c, i + 1, raw);
            } else {
                // 像是一颗二叉树，在这里发生了分叉，每一个分支遍历到
                dfs(result, cur + Character.toLowerCase(c), i + 1, raw);
                dfs(result, cur + Character.toUpperCase(c), i + 1, raw);
            }
        }
    }
}

什么时候用for来着？比如电话号码的字母组合，每一个节点有k种决策，且k个数不定，用for写比较好。如果k个数确定（比如二叉树2个，或者图遍历4个方向），就可以不用for，直接全枚举出来。

再回头看子集，为什么for也行，枚举二叉树的每一个分支也行？因为每一个节点都可要可不要，这个时候有不同的实现方式：

  1. 官方视角里，“可要可不要”就是每一个节点做两种决策，最终遍历到最后一个字符，所有情况就都收集了；
  2. 我的那个解法的视角里，“可要可不要”是通过for来做的，i++的时候，就是说在这个节点上没有要i。但实际上因为用了for，我的每一个节点都在做类似全排列的事情。

总体来说，结果对了，不代表整个试探过程是有效的。可能像我一样在做瞎试探，最终只取了符合条件的，结果依然对，但实际瞎试探了非常多种情况。

子集 II可以用同样的思路，不过在剪枝方面会比较麻烦。比如1, 2, 2, 2，对于这一连串2，可以选择0/1/2/3个，分别构成不同的子集。怎么避免出现[1, 第一个2]，[1, 第二个2]这种重复结果呢？

  1. 如果前一个和当前数字相同，且前一个没选，则当前也不要选！这样可以避免重复。
  2. 如果前一个选了，当前可选可不选：如果选了，就是两个2，符合子集；如果不选，就是一个2，结合第一条规则，后面的2都不会被选，所以就是只有一个2的子集；

这样，所有的0/1/2/3个2的情况都被考虑到了：

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

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // sort
        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        dfs(result, 0, new ArrayList<>(), nums, false);

        return result;
    }

    private void dfs(List<List<Integer>> result, int i, List<Integer> cur, int[] nums, boolean choosePre) {
        if (i == nums.length) {
            result.add(new ArrayList<>(cur));
            return;
        }

        int curInteger = nums[i];

        // 如果前一个数和我相同，且没选，那我一定不选
        if (i > 0 && curInteger == nums[i - 1] && !choosePre) {
            // without cur integer
            dfs(result, i + 1, cur, nums, false);
            return;
        }

        // 否则我可选可不选
        
        cur.add(curInteger);
        // with cur integer
        dfs(result, i + 1, cur, nums, true);
        cur.removeLast();

        // without cur integer
        dfs(result, i + 1, cur, nums, false);
    }
}

这个题的去重还有比较狗的地方：因为题目给出了限定，元素最多有10个，所以可以暴力dfs所有可能，然后使用set去重（Set<List<Integer>> result）。为了set去重方便，可以给原数组排序，这样所有子集都是单调的，相同子集就会只留一个。如果实在想不出来怎么剪枝，可以结合题目规模，考虑这种方案。

这个题的剪枝和组合总和 II有点儿像又不一样：

  • 组合总和 II是每一层都有多个选择，如果上一层选了，本层可选可不选；但本层如果选了，本层后面的决策一定不要再选了；
  • 本题每一层只有两个选择，如果上一层选了，本层可选可不选；但如果上一层没选，本层一定不要选了；

从图的角度再理解DFS和BFS

dfs和bfs在树里很常用。但是，在网格里二者也很常用！只不过树天然是有向图，不会重复，但是格子是无向图，所以网格的遍历要有目的性，需要进行标记，代表来过，如果不标记，会重复走回去。

DFS与网格

比如岛屿周长，就是dfs走遍一个岛屿。

这些dfs算法可以为我们上面的dfs补充一些知识：

  1. 格子的dfs就四种情况，for循环或者直接写都行；
  2. 先判断再决定是否进入dfs？还是先进去，不满足再返回？都行。上面的组合总和II里的sum我们用的是后者，岛屿问题这里用的也是后者，因为这样判断起来更简单；
  3. 如果dfs本身无限重复递归，或者从形象的角度来说会走重复的路，不像树一样是有向无环的，那我们就手动给它加个界（染色标记）；

这样岛屿的周长就迎刃而解了：

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

public int islandPerimeter(int[][] grid) {
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                // 题目限制只有一个岛屿，计算一个即可
                return dfs(grid, r, c);
            }
        }
    }
    return 0;
}

int dfs(int[][] grid, int r, int c) {
    if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) {
        return 1;
    }
    if (grid[r][c] == 0) {
        return 1;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
    return dfs(grid, r - 1, c)
        + dfs(grid, r + 1, c)
        + dfs(grid, r, c - 1)
        + dfs(grid, r, c + 1);
}

这里没有使用result去收集结果，因为就一个值。把每一种dfs收集到的结果（每一个方向的探索结果）加起来即可，就和求树的高度/叶子节点的个数一样。

岛屿问题的难点在于问题的转化：如何把所求内容转化为和DFS/BFS相关的问题。

  • 岛屿周长：从某个1开始DFS，如果拓展的该方向上的下一个是0，就是周长，记录个1（上述解法中，是return 1）；
  • 岛屿数量：从某个1开始DFS，消除所达之处所有的1，看能这么玩几次，就说明有几个岛屿；
  • 最大的岛屿的面积：和岛屿数量一样，其实就是在消除一个岛屿的时候，记录下该岛屿的面积，最后求个max（求岛屿面积和求周长是一样的，也是四个方向上探索结果的累加）；

最大的岛屿的面积：

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

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    max = Math.max(max, dfs(grid, i, j));
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int x, int y) {
        int row = grid.length;
        int col = grid[0].length;
        if (x < 0 || x >= row || y < 0 || y >= col) {
            return 0;
        }

        if (grid[x][y] == 0 || grid[x][y] == 2) {
            return 0;
        }

        // 到此一游
        // 直接标记为0也行，相当于把岛屿抹去了，反正也用不到了
        grid[x][y] = 2;
        
        return 1 + dfs(grid, x - 1, y)
        + dfs(grid, x + 1, y)
        + dfs(grid, x, y - 1)
        + dfs(grid, x, y + 1);
    }
}

BFS与网格 - 层序遍历/最短路径

bfs遍历图的方式，其实和遍历树的方式差不多：

  • 每一个符合条件的点都作为root，加入队列；
  • 依次pop队列，每一个pop出来的点拓展出上下左右四个点，如果满足条件，再加入队列；
  • 当然，拓展点的时候也要做标记，因为是多个root，防止冲突扩散；

从题解中可以看出来，如果抽象能力再强一些，可以很容易看出图和树在BFS上的共同点：

  • 单源多源：tree只有1个root，而图可以有多个源点，所以首先需要把多个源点都入队。
  • 有向无向：tree是有向的因此不需要标志是否访问过，而对于无向图来说，必须得标志是否访问过！并且为了防止某个节点多次入队，需要在入队之前就将其设置成已访问！

BFS和DFS都能遍历所有节点。在掌握dfs之后，发现dfs其实比bfs更好写。那为什么要用BFS？在BFS 的使用场景总结里说的很好，bfs有dfs没有的两个优势：

  1. 层序遍历；
  2. 最短路径；

层序遍历自不必说，必须层序输出一个树的节点，只有bfs能做到。另一个点比较难注意：bfs更适用于那些求距离的题目，比如离陆地最远的海洋，怎么转化呢？

  • 从每一个1出发，开始BFS，看最远被标记到的数是几。bfs是同时走的，和dfs不一样，不是先让一个root走到头；
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

class Solution {
    public int maxDistance(int[][] grid) {
        // 用数组表示点的横纵坐标
        Deque<int[]> queue = new ArrayDeque<>();

        int row = grid.length;
        int col = grid[0].length;

        // 把陆地加入队列，一层层遍历
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }

        // 特例，没有海洋
        if (queue.size() == row * col) {
            return -1;
        }

        int[] x = new int[] {-1, 1, 0, 0};
        int[] y = new int[] {0, 0, -1, 1};

        int distance = 0;
        while (!queue.isEmpty()) {
            distance++;
            int size = queue.size();
            while (size-- > 0) {
                int[] point = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int a = point[0] + x[i];
                    int b = point[1] + y[i];
                    if (a < 0 || a >= row || b < 0 || b >= col) {
                        continue;
                    }

                    // 新的海洋
                    if (grid[a][b] == 0) {
                        // 标记来过
                        grid[a][b] = distance;
                        queue.offer(new int[] {a, b});
                    }
                }
            }
        }

        return distance - 1;
    }
}

这个是多源bfs，但是无论是一个点的bfs还是多个点的bfs，本质上没有区别。毕竟单个点的bfs从第二层开始，也变成多点了嘛！

但并不是所有的bfs都和最短路径配合。比如最小高度树，如果单从一个点看，求一棵树的最小高度直接用的是bfs最短路径。但是如果求全局的最小，其实是每次从叶节点bfs到最中间的核心点，此时每次入队的不是临近节点，而是新的度为1的节点。

bfs与Dijkstra

说到最短路径，就想到Dijkstra，二者的区别在于：bfs只适合求没有权重时候的最短路径，权重不同时还得看迪杰斯特拉！

DFS总结

  • 终结条件
  • 情况选择
  • 剪枝
  • 参数列表
  • 返回值（返回方式）

通用dfs基本都是前序。如果是树，dfs的时候考虑一下要不要用后序（从下往上思考问题）。

本文由作者按照 CC BY 4.0 进行授权