回溯
理论基础
「回溯算法 backtracking algorithm」是一种通过穷举来解决问题的方法,它的核心思想是从一个初始状态出发,暴力搜索所有可能的解决方案,当遇到正确的解则将其记录,直到找到解或者尝试了所有可能的选择都无法找到解为止,所以回溯算法也通常采用“深度优先搜索”来遍历解空间。
回溯法解决的问题
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。
二叉树例子
题目
1
| 给定一个二叉树,搜索并记录所有值为 7 的节点,请返回节点列表
|
![img](https://pic.imgdb.cn/item/6565a520c458853aef6e2cb0.png)
题解
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](https://pic.imgdb.cn/item/6565a4dec458853aef6d60f0.png)
简单组合例子
1
| 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
|
例如 n = 4、 k = 3
,相当于我们在 [1,2,3,4
]中取 3
个数组合 则图解应为
![img](https://pic.imgdb.cn/item/6565a9cdc458853aef7ba00b.png)
代码:
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](https://pic.imgdb.cn/item/6565b200c458853aef9446af.png)
代码:
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 算法
代码随想录