回溯法

, ,

定义：

  • 回溯算法是类似于枚举的过程，在搜索过程中寻找满足条件的解，当不满足条件时，就退回重新选择。经常被用在深度优先搜索（DFS）和广度优先搜索（BFS）的技巧。关键点是：走不通就回头。

算法过程：

  1. 构造空间树：通过构造空间树来搜索所有可能的结果，树的一个节点代表了问题的一个状态。从根节点开始，逐步向下扩展，直到叶子节点。
  2. 遍历：在回溯算法中，遍历过程实际上是深度优先搜索的过程。
  3. 如遇到边界条件，即不再向下搜索，转而搜索另一条链：当遇到错误状态或无法继续遍历时，会回溯到上一个状态，即 “走不通就回头”。
  4. 达到目标条件，输出结果。

例题

中心对称数：

给定一个整数 n ，返回所有长度为 n 的 中心对称数 。你可以以 任何顺序 返回答案。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:

输入： n = 2
输出：[“11”,”69”,”88”,”96”]

示例 2:

输入： n = 1
输出：[“0”,”1”,”8”]

解析：

由题意得，满足条件的数字分别有 0 和 0、1 和 1、8 和 8、6 和 9、9 和 6 这五种情况，其中 0 不能不是开头（即不能有前缀零），69 这两个数不能在数字的**”中心”。**

答案：

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
class Solution {
    List<String> res = new ArrayList<>();
    char[] path;

    public List<String> findStrobogrammatic(int n) {
        path = new char[n];
        
        backtracking(n, 0, n - 1);
        return res;
    }

    private void backtracking(int n, int left, int right) {
        //终止条件
        if(left > right) {
            res.add(new String(path));
            return;
        }

        //除长度为1的情况，首位非0
        if(left > 0 || n == 1) {
            path[left] = '0';
            path[right] = '0';
            backtracking(n, left + 1, right - 1);
        }

        //前后为1的情况
        path[left] = '1';
        path[right] = '1';
        backtracking(n, left + 1, right - 1);

        //前后为8的情况
        path[left] = '8';
        path[right] = '8';
        backtracking(n, left + 1, right - 1);

        //不是中心时，前后为69的情况
        if(left != right){
            path[left] = '6';
            path[right] = '9';
            backtracking(n, left + 1, right - 1);

            path[left] = '9';
            path[right] = '6';
            backtracking(n, left + 1, right - 1);
        }
    }
}

相关链接：

247. 中心对称数 II - 力扣（LeetCode）

回溯法 - OI Wiki

yzlzzzdeveloper