回溯

理论基础

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止，所以回溯算法也通常采用“深度优先搜索”来遍历解空间。

回溯法解决的问题

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

二叉树例子

题目
1
给定一个二叉树，搜索并记录所有值为 7 的节点，请返回节点列表

img

题解
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
## 回溯

#### 理论基础

「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止，所以回溯算法也通常采用“深度优先搜索”来遍历解空间。

#### 回溯法解决的问题

- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等

#### 如何理解回溯法

**回溯法解决的问题都可以抽象为树形结构**，**集合的大小就构成了树的宽度，递归的深度，都构成的树的深度**。



#### 二叉树例子

##### 题目

```css
给定一个二叉树，搜索并记录所有值为 7 的节点，请返回节点列表
```



![](https://pic.imgdb.cn/item/6565a520c458853aef6e2cb0.png)

##### 题解

```java
/* 前序遍历： */
void preOrder(TreeNode root) {
    // 递归到终止节点
    if (root == null) {
        return;
    }
    if (root.val == 7) {
        // 记录解
        res.add(root);
    }
    preOrder(root.left);
    preOrder(root.right);
}

```

此时，我们遍历的顺序就是  ` 1-3-2-5-4-7-6`  ，也可以从下图中看出。



![](https://pic.imgdb.cn/item/6565a4dec458853aef6d60f0.png)

#### 简单组合例子

```yaml
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
```

例如  `n = 4、 k = 3`  ，相当于我们在 `[1,2,3,4`]中取 `3` 个数组合 则图解应为

![](https://pic.imgdb.cn/item/6565a9cdc458853aef7ba00b.png)

代码：

```java
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        int[] ints = new int[n];
        for (int i = 1; i <= n; i++) {
            ints[i-1] = i;
        }

        dfs(0,k,ints);

        return result;

    }
    private void dfs(int start,int k,int[] ints){

        if(path.size() == k)
            result.add(new ArrayList<>(path));

        if(start >= ints.length || path.size() >= k) return;

        for (int i = start; i < ints.length; i++) {
            path.add(ints[i]);
            dfs(i+1,k,ints);
            path.remove(path.size()-1);
        }


    }
```

代码暂且不管，从图中可以看到，我们将这个问题转化为一个树形遍历， 将回溯问题 转换为 数层遍历有助于我们理解回溯的过程。

#### 尝试与回退

**之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略**。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

##### 尝试

在进入递归后紧接着就是 逻辑判断 的 `return` 语句，它会在尝试失败后返回到上一层递归，从树形结构理解就是返回到了它的父节点。

##### 回退

通常使用`path` 记录递归调用的路径，也就是大部分情况下的符合条件的解，当递归返回时，路径也要相应的回退

例如上述图解，我们在 `[1-2-3]` 得到一个满足的解后，程序 `return`, 这时需要弹出`path`中最后一个元素，也就是 使递归层 回到  `[1-2]`

##### 例子

在上述的二叉树例题中，如果要获取节点的路径呢？

```yaml
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径。
```

题解：

```java
/* 前序遍历：例题二 */
void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}

```

**`path` ：路径，也就是满足条件的一条解。**

#### 剪枝

复杂的回溯问题通常包含一个或多个约束条件，**约束条件通常可用于“剪枝”**。

```yaml
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，**并要求路径中不包含值为 3 的节点**。
```

这样的话，我们就需要剪枝，简单来说，就是增加递归的限定条件，不满足条件的路径会提前弹出

图示：

![](https://pic.imgdb.cn/item/6565b200c458853aef9446af.png)

代码：

```java
void preOrder(TreeNode root) {
    // 剪枝
    if (root == null || root.val == 3) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}
```

剪枝操作不止在限定条件中，如 **简单组合例子** 中，横向遍历了 第一层 数值， 在下面的递归层级中，`start`都增加了 `1`

```java
 for (int i = start; i < ints.length; i++) {
            path.add(ints[i]);
            dfs(i+1,k,ints);
            path.remove(path.size()-1);
       }
```

这样 下一层级节点就从 `i+1`开始，这样就减少了  当前值的层级，相当于剪枝。



#### 框架代码

```java
// 结果集
private List  result;
// 路径
private List path

/* 回溯算法框架 */
void backtrack(int start, List<Choice> choices,) {
    // 判断是否为解
    if (isSolution(start)) {
        // 记录解
       	result.add(path)
        // 停止继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

```



#### 参考

[HELLO 算法](https://www.hello-algo.com/chapter_backtracking/backtracking_algorithm/#1316)

[代码随想录](https://www.programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%A2%98%E7%9B%AE%E5%88%86%E7%B1%BB)

此时，我们遍历的顺序就是 1-3-2-5-4-7-6 ，也可以从下图中看出。

img

简单组合例子

1
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

例如 n = 4、 k = 3 ，相当于我们在 [1,2,3,4]中取 3 个数组合 则图解应为

img

代码：

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
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
    int[] ints = new int[n];
    for (int i = 1; i <= n; i++) {
        ints[i-1] = i;
    }

    dfs(0,k,ints);

    return result;

}
private void dfs(int start,int k,int[] ints){

    if(path.size() == k)
        result.add(new ArrayList<>(path));

    if(start >= ints.length || path.size() >= k) return;

    for (int i = start; i < ints.length; i++) {
        path.add(ints[i]);
        dfs(i+1,k,ints);
        path.remove(path.size()-1);
    }


}

代码暂且不管，从图中可以看到，我们将这个问题转化为一个树形遍历， 将回溯问题 转换为 数层遍历有助于我们理解回溯的过程。

尝试与回退

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。

尝试

在进入递归后紧接着就是 逻辑判断 的 return 语句，它会在尝试失败后返回到上一层递归，从树形结构理解就是返回到了它的父节点。

回退

通常使用path 记录递归调用的路径，也就是大部分情况下的符合条件的解，当递归返回时，路径也要相应的回退

例如上述图解，我们在 [1-2-3] 得到一个满足的解后，程序 return, 这时需要弹出path中最后一个元素，也就是 使递归层 回到 [1-2]

例子

在上述的二叉树例题中，如果要获取节点的路径呢？

1
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径。

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 前序遍历：例题二 */
void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}

path ：路径，也就是满足条件的一条解。

剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。

1
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，**并要求路径中不包含值为 3 的节点**。

这样的话，我们就需要剪枝，简单来说，就是增加递归的限定条件，不满足条件的路径会提前弹出

图示：

img

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(TreeNode root) {
    // 剪枝
    if (root == null || root.val == 3) {
        return;
    }
    // 尝试
    path.add(root);
    if (root.val == 7) {
        // 记录解
        res.add(new ArrayList<>(path));
    }
    preOrder(root.left);
    preOrder(root.right);
    // 回退
    path.remove(path.size() - 1);
}

剪枝操作不止在限定条件中，如 简单组合例子 中，横向遍历了 第一层 数值， 在下面的递归层级中，start都增加了 1

1
2
3
4
5
for (int i = start; i < ints.length; i++) {
           path.add(ints[i]);
           dfs(i+1,k,ints);
           path.remove(path.size()-1);
      }

这样 下一层级节点就从 i+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
// 结果集
private List  result;
// 路径
private List path

/* 回溯算法框架 */
void backtrack(int start, List<Choice> choices,) {
    // 判断是否为解
    if (isSolution(start)) {
        // 记录解
       	result.add(path)
        // 停止继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

参考

HELLO 算法

代码随想录