关于递归与回溯的想法

发表于 | 分类于

前言


在刷过一些搜索相关算法题之后，BFS类的题实现都比较简单，我的关注点主要在DFS上，相关的算法题非常多，而回溯作为DFS中的一种，可以解决全排列、组合等等的一系列问题。

排列问题

LeetCode 46：给定一个没有重复数字的序列，返回其所有可能的全排列。

1
2
e.g. 输入[1, 2, 3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这类问题往往都可以通过暴力求解，比如通过n个for循环来实现穷举，但是由于我们并不知道n的具体数量，所以很难通过一般的穷举实现，所以需要借助递归来实现，而往往这类问题是需要回溯的，也就是说，在完成同层之后需要返回到之前的状态，继续做该层的问题，借助简单的图来说明一下，在完成1->2之后需要返回1的状态，这时候就要把2去除，目的是为了做同层的1->3的排列，同样的在完成1->2->3之后需要返回2的状态，虽然2只有一个选择。

1
2
3
4
5
  1      2      3
/  \  
   2   3    ...   ...
   |   |
          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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 回溯
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        List<Integer> tmp = new ArrayList<>();
        backTracing(nums, result, tmp);
        return result;
    }

    public void backTracing(int[] nums, List<List<Integer>> result, List<Integer> tmp) {
        if (tmp.size() == nums.length) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0 ; i < nums.length ; ++i) {
            if (!tmp.contains(nums[i])) {
                tmp.add(nums[i]);
                backTracing(nums, result, tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

LeetCode 17 电话号码的字母组合：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

1
2
3
e.g. 
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

这题可以回溯去做，这边也算是有个小小的坑要记录一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<String> letterCombinations(String digits) {
    // dfs 回溯
    String[] pattern = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    if (digits.equals("")) {
        return result;
    }
    backTracing(new StringBuilder(), digits, pattern, result);
    System.out.println(result);
    return result;
}

public void backTracing(StringBuilder sb, String digits, String[] pattern, List<String> result) {
    if (sb.length() == digits.length()) {
        result.add(sb.toString());
        return;
    }
    String p = pattern[digits.charAt(sb.length()) - '0'];
    for (char each : p.toCharArray()) {
        sb.append(each);
        backTracing(sb, digits, pattern, result);
        sb.deleteCharAt(sb.length()-1);
    }
}

这边用的是StringBuilder去做的，其实也能用普通的String去做，这样做的速度会慢一些，但是注意了，用String可以不用去做删减的操作，因为对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
public List<String> letterCombinations(String digits) {
    // 也可以用普通的dfs去做，不用考虑回溯
    String[] pattern = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    if (digits.equals("")) {
        return result;
    }
    backTracing("", digits, pattern, result);
    return result;
}

public void backTracing(String sb, String digits, String[] pattern, List<String> result) {
    if (sb.length() == digits.length()) {
        System.out.println(sb);
        result.add(sb);
        return;
    }
    System.out.println(sb);
    String p = pattern[digits.charAt(sb.length()) - '0'];
    for (char each : p.toCharArray()) {
        //            sb = sb+each;
        //            backTracing(sb, digits, pattern, result);
        //            sb = sb.substring(0, sb.length()-1);
        // 上下两种写法一样
        backTracing(sb+each, digits, pattern, result);
    }
}

这种排列问题可以产生多种规则的题目，比如Leetcode的47题，给出的数组是有重复数字的，因此这边考虑到最后组合的结果不能产生重复的结果，所以就要避免重复组合的产生，比如说[1,1,2]，考虑用set去重是一种思路，但是时间和空间都比较浪费，这边最好的方法是采用剪枝，比如第一个1和第二个1其实是两个一样的分支，最终产生的结果是一样的，所以考虑把第二个1的分支剪掉，同样的以2打头的，2和另外两个1排列也是一样的结果，所以也要剪枝。总结一下这边最重要的步骤是对相同数字剪枝，所以我们可以考虑将数组先排列一下，让相同的数字在一起，然后再在进行回溯的时候进行剪枝，剪枝的条件是当前的这个数等于之前的数，并且之前的那个数还没有被遍历到，这就是遍历到第二个1的时候的情况，此时由于回溯，第一个1的visit状态是false，此时这种分支就被剪枝。

1
2
3
4
// 剪枝
if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
    continue;
}

组合问题

组合问题和排列问题是类似的解题思路，比如Leetcode的77题，从多个数中取k个数进行组合的问题。要考虑的还是那几个问题，一个是递归结束条件为tmp数组中的数字达到k个。一个是递归下层的由于不考虑数字的重复，要从i+1开始。最后一个是删除最后一个改变的状态，回溯到之前的状态。相类似的题目还有39题、40题、216题、78题、90题

二维的问题

之前的排列问题或者组合问题都是针对一维的数组进行回溯求解的，也有很多的二维平面上回溯的问题，比如Leetcode的79题，但是求解的思路还是和之前的问题是类似的，要把握三个点，一个是递归的结束条件，一个是下一层递归的条件，最后一个是状态的恢复。来看这道题的解答部分

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
int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean exist(char[][] board, String word) {
    // dfs + 回溯
    if (board.length == 0) {
        if (word.equals("")) {
            return true;
        } else {
            return false;
        }
    }

    int m = board.length;
    int n = board[0].length;
    boolean[][] flag = new boolean[m][n];
    for (int i = 0 ; i < m ; ++i) {
        for (int j = 0 ; j < n ; ++j) {
            if (backTracing(board, flag, i, j, m, n, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

public boolean backTracing(char[][] board, boolean[][] flag, int i, int j, int m, int n, String word, int k) {
    // 递归的结束条件
    if (k == word.length()) {
        return true;
    }
    // 剪枝
    if (i<0 || j<0 || i>=m || j>=n || board[i][j]!=word.charAt(k) || flag[i][j]) {
        return false;
    }
    // 四个方向上的递归调用
    flag[i][j] = true;
    for (int[] eachDirect : direct) {
        int x = i+eachDirect[0];
        int y = j+eachDirect[1];
        if (backTracing(board, flag, x, y, m, n, word, k+1)) {
            return true;
        }
    }
    // 状态的恢复
    flag[i][j] = false;
    return false;
}

这种二维平面上的题目还有一种是不需要回溯的，只需要普通的DFS就能求解的问题，比如说Leetcode的130、200、417、547、695等问题。

二维平面上回溯的问题类似的还有Leetcode的37题，这题我感觉还是比较难的，是一个数独的问题，和N皇后问题类似，需要考虑每个位置的多种状态，从而来尝试最终的解。