Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5781e5e

Browse files
Update
1 parent2c96000 commit5781e5e

File tree

4 files changed

+154
-101
lines changed

4 files changed

+154
-101
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -126,6 +126,8 @@
126126
*[二叉树：搜索树转成累加树](https://mp.weixin.qq.com/s/hZtJh4T5lIGBarY-lZJf6Q)
127127
*[二叉树：总结篇！（需要掌握的二叉树技能都在这里了）](https://mp.weixin.qq.com/s/-ZJn3jJVdF683ap90yIj4Q)
128128

129+
* 回溯算法
130+
*[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)
129131

130132
（持续更新中....）
131133

‎problems/0077.组合.md

Lines changed: 88 additions & 96 deletions
Original file line numberDiff line numberDiff line change
@@ -1,94 +1,100 @@
11

2+
>回溯法的第一道题目，就不简单呀！
3+
24
#第77题. 组合
35

46
题目链接：https://leetcode-cn.com/problems/combinations/
57

6-
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
7-
示例:
8-
9-
输入: n = 4, k = 2
10-
输出:
11-
[
12-
[2,4],
13-
[3,4],
14-
[2,3],
15-
[1,2],
16-
[1,3],
17-
[1,4],
18-
]
8+
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
199

10+
示例:
11+
输入: n = 4, k = 2
12+
输出:
13+
[
14+
[2,4],
15+
[3,4],
16+
[2,3],
17+
[1,2],
18+
[1,3],
19+
[1,4],
20+
]
2021

2122
#思路
2223

23-
这是回溯法的经典题目。
24+
本题这是回溯法的经典题目。
2425

25-
直觉上当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
26+
直接的解法当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
2627

2728
代码如下：
2829
```
29-
int n = 4;
30-
for (int i = 1; i <= n; i++) {
31-
for (int j = i + 1; j <= n; j++) {
32-
cout << i << " " << j << endl;
33-
}
30+
int n = 4;
31+
for (int i = 1; i <= n; i++) {
32+
for (int j = i + 1; j <= n; j++) {
33+
cout << i << " " << j << endl;
3434
}
35+
}
3536
```
3637

3738
输入：n = 100, k = 3
3839
那么就三层for循环，代码如下：
3940

4041
```
42+
int n = 100;
4143
for (int i = 1; i <= n; i++) {
4244
for (int j = i + 1; j <= n; j++) {
43-
for (int u = j + 1; u <=n; n++) {
44-
45+
for (int u = j + 1; u <=n; n++) {
46+
cout << i << " " << j << " " << u << endl;
4547
}
4648
}
4749
}
4850
```
4951

5052
**如果n为100，k为50呢，那就50层for循环，是不是开始窒息**。
5153

52-
那么回溯法就能解决这个问题了。
54+
**此时就会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！**
5355

54-
回溯是用来做选择，递归用来做节点层叠嵌套（可以理解是随便开K的for循环），**每一次的递归相当于嵌套一个for循环，可以用于解决多层嵌套循环的问题了**。
56+
咋整？
5557

56-
**回溯问题都可以抽象为一棵树形结构！用树形结构来理解回溯就容易多了**。
58+
回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。
5759

58-
那么我们把组合问题抽象为如下树形结构：
60+
那么回溯法怎么暴力搜呢？
5961

60-
<imgsrc='../pics/77.组合.png'width=600> </img></div>
62+
上面我们说了**要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题**。
6163

62-
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
64+
递归来做层叠嵌套（可以理解是开k层for循环），**每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了**。
65+
66+
此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。
6367

64-
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取，2，3，4， 得到集合[1,2][1,3][1,4]，以此类推。
68+
一些同学本来对递归就懵，回溯法中递归还要嵌套for循环，可能就直接晕倒了！
6569

66-
**回溯的问题都可以抽象为一个树形结构，在求解组合问题的过程中，n相当于树的宽度，k相当于树的深度**。
70+
如果脑洞模拟回溯搜索的过程，绝对可以让人窒息，所以需要抽象图形结构来进一步理解。
6771

68-
**每次从集合中选组元素，可选择的范围随着选择的进行而限缩，调整可选择的范围**
72+
**我们在[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)中说道回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了**。
6973

70-
如何在这个树上遍历，然后收集到我们要的结果集呢？
74+
那么我把组合问题抽象为如下树形结构：
7175

72-
用的就是回溯搜索法，**可以发现，每次搜索到了叶子节点，我们就找到了一个结果**。
76+
<imgsrc='../pics/77.组合.png'width=600> </img></div>
7377

78+
可以看出这个棵树，一开始集合是 1，2，3，4， 从左向右取数，取过的数，不在重复取。
7479

75-
**一些同学对递归操作本来就不熟练，递归上面又加上一个for循环，直接晕倒！**
80+
第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2][1,3][1,4]，以此类推。
7681

77-
##
82+
**每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围**。
7883

79-
我再给大家捋顺一下。
84+
**图中可以发现n相当于树的宽度，k相当于树的深度**。
8085

81-
这个backtracking（递归函数）是从根节点向树的叶子节点方向遍历，**for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历**，这样就把这棵树全遍历完了，如图所示：
86+
那么如何在这个树上遍历，然后收集到我们要的结果集呢？
8287

83-
<imgsrc='../pics/77.组合1.png'width=600> </img></div>
88+
**图中每次搜索到了叶子节点，我们就找到了一个结果**。
8489

85-
backtracking一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回，那么backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
90+
相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
8691

87-
##求组合
92+
在[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)中我们提到了回溯法三部曲，那么我们按照回溯法三部曲开始正式讲解代码了。
8893

89-
掌握了模板之后，我们再来看一下这道求组合的题目。
9094

91-
* 回溯函数返回值以及参数
95+
##回溯法三部曲
96+
97+
* 递归函数的返回值以及参数
9298

9399
在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
94100

@@ -99,14 +105,16 @@ vector<vector<int>> result; // 存放符合条件结果的集合
99105
vector<int> path; // 用来存放符合条件结果
100106
```
101107

102-
其实不定义这两个全局遍历也是可以的，把这两个变量放进回溯函数的参数里，但为了函数里参数太多影响可读性，所以我定义全局变量。
108+
其实不定义这两个全局遍历也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
103109

104-
首先两个参数，集合n里面取k的数，是两个int型的变量。
110+
函数里一定有两个参数，既然是集合n里面取k的数，那么n和k是两个int型的参数。
105111

106-
然后还需要一个参数，也为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
112+
然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
107113

108114
为什么要有这个startIndex呢？
109115

116+
**每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex**。
117+
110118
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。
111119

112120
<imgsrc='../pics/77.组合2.png'width=600> </img></div>
@@ -125,7 +133,7 @@ void backtracking(int n, int k, int startIndex)
125133

126134
什么时候到达所谓的叶子节点了呢？
127135

128-
就是path这个数组的大小如果达到k，说明我们找到了一个集合大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
136+
path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
129137

130138
如图红色部分：
131139

@@ -142,26 +150,30 @@ if (path.size() == k) {
142150
}
143151
```
144152

153+
* 单层搜索的过程
145154

146-
* 回溯搜索的遍历过程
155+
回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
147156

148-
在如下如中，我们知道for循环用来横向遍历，递归的过程是纵向遍历。
149157
<imgsrc='../pics/77.组合1.png'width=600> </img></div>
150158

151159
如此我们才遍历完图中的这棵树。
152160

153-
那么for循环每次就是从startIndex开始遍历，然后用path保存每次遍历到的节点。
161+
for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
154162

155163
代码如下：
156164

157165
```
158-
for (int i = startIndex; i <= n; i++) {
166+
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
159167
path.push_back(i); // 处理节点
160-
backtracking(n, k, i + 1); // 注意下一层搜索要从i+1开始
168+
backtracking(n, k, i + 1); //递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
161169
path.pop_back(); // 回溯，撤销处理的节点
162170
}
163171
```
164172

173+
可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
174+
175+
backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
176+
165177
关键地方都讲完了，组合问题C++完整代码如下：
166178

167179

@@ -177,71 +189,51 @@ private:
177189
}
178190
for (int i = startIndex; i <= n; i++) {
179191
path.push_back(i); // 处理节点
180-
backtracking(n, k, i + 1);
192+
backtracking(n, k, i + 1); // 递归
181193
path.pop_back(); // 回溯，撤销处理的节点
182194
}
183195
}
184196
public:
185197
vector<vector<int>> combine(int n, int k) {
186-
result.clear();// 可以不写
187-
path.clear(); // 可以不写
198+
result.clear(); // 可以不写
199+
path.clear();// 可以不写
188200
backtracking(n, k, 1);
189201
return result;
190202
}
191203
};
192204
```
193205

194-
##剪枝优化
195-
196-
在遍历的过程中如下代码 ：
206+
还记得我们在[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)中给出的回溯法模板么？
197207

208+
如下：
198209
```
199-
for (int i = startIndex; i <= n; i++)
200-
```
201-
202-
这个遍历的范围是可以剪枝优化的，怎么优化呢？
203-
204-
来举一个例子，n = 4， k = 4的话，那么从2开始的遍历都没有意义了。
205-
206-
已经选择的元素个数：path.size();
210+
void backtracking(参数) {
211+
if (终止条件) {
212+
存放结果;
213+
return;
214+
}
207215
208-
要选择的元素个数 : k - path.size();
216+
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
217+
处理节点;
218+
backtracking(路径，选择列表); // 递归
219+
回溯，撤销处理结果
220+
}
221+
}
222+
```
209223

210-
在集合n中开始选择的起始位置 : n - (k - path.size());
224+
**对比一下本题的代码，是不是发现有点像！** 所以有了这个模板，就有解题的大体方向，不至于毫无头绪。
211225

212-
因为起始位置是从1开始的，而且代码里是n <= 起始位置，所以 集合n中开始选择的起始位置 : n - (k - path.size()) + 1;
226+
#总结
213227

214-
所以优化之后是：
228+
组合问题是回溯法解决的经典问题，我们开始的时候给大家列举一个很形象的例子，就是n为100，k为50的话，直接想法就需要50层for循环。
215229

216-
```
217-
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)
218-
```
230+
从而引出了回溯法就是解决这种k层for循环嵌套的问题。
219231

220-
优化后整体代码如下：
232+
然后进一步把回溯法的搜索过程抽象为树形结构，可以直观的看出搜索的过程。
221233

222-
```
223-
class Solution {
224-
private:
225-
vector<vector<int>> result; // 存放符合条件结果的集合
226-
vector<int> path; // 用来存放符合条件结果
227-
void backtracking(int n, int k, int startIndex) {
228-
if (path.size() == k) {
229-
result.push_back(path);
230-
return;
231-
}
232-
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
233-
path.push_back(i); // 处理节点
234-
backtracking(n, k, i + 1);
235-
path.pop_back(); // 回溯，撤销处理的节点
236-
}
237-
}
238-
public:
234+
接着用回溯法三部曲，逐步分析了函数参数、终止条件和单层搜索的过程。
239235

240-
vector<vector<int>> combine(int n, int k) {
241-
backtracking(n, k, 1);
242-
return result;
243-
}
244-
};
245-
```
236+
**本题其实是可以剪枝优化的，大家可以思考一下，具体如何剪枝我会在下一篇详细讲解，敬请期待！**
246237

238+
**就酱，如果对你有帮助，就帮Carl转发一下吧，让更多的同学发现这里！**
247239

‎problems/0077.组合优化.md

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
2+
##剪枝优化
3+
4+
我们说过，回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。
5+
6+
在遍历的过程中有如下代码 ：
7+
8+
```
9+
for (int i = startIndex; i <= n; i++)
10+
```
11+
12+
这个遍历的范围是可以剪枝优化的，怎么优化呢？
13+
14+
来举一个例子，n = 4， k = 4的话，那么从2开始的遍历都没有意义了。
15+
16+
所以，可以优化递归中每一层中for循环搜索的起始位置。
17+
18+
优化过程如下：
19+
20+
1. 已经选择的元素个数：path.size();
21+
22+
2. 要选择的元素个数 : k - path.size();
23+
24+
3. 在集合n中开始选择的起始位置 : n - (k - path.size());
25+
26+
因为起始位置是从1开始的，而且代码里是n <= 起始位置，所以 集合n中开始选择的起始位置 : n - (k - path.size()) + 1;
27+
28+
所以优化之后是：
29+
30+
```
31+
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)
32+
```
33+
34+
优化后整体代码如下：
35+
36+
```
37+
class Solution {
38+
private:
39+
vector<vector<int>> result; // 存放符合条件结果的集合
40+
vector<int> path; // 用来存放符合条件结果
41+
void backtracking(int n, int k, int startIndex) {
42+
if (path.size() == k) {
43+
result.push_back(path);
44+
return;
45+
}
46+
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
47+
path.push_back(i); // 处理节点
48+
backtracking(n, k, i + 1);
49+
path.pop_back(); // 回溯，撤销处理的节点
50+
}
51+
}
52+
public:
53+
54+
vector<vector<int>> combine(int n, int k) {
55+
backtracking(n, k, 1);
56+
return result;
57+
}
58+
};
59+
```

‎problems/算法模板.md

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -222,16 +222,16 @@ int countNodes(TreeNode* root) {
222222
```
223223

224224
##回溯算法
225-
226225
```
227-
backtracking() {
226+
voidbacktracking(参数) {
228227
if (终止条件) {
229228
存放结果;
229+
return;
230230
}
231231
232-
for (选择：选择列表（可以想成树中节点孩子的数量）) {
233-
递归，处理节点;
234-
backtracking();
232+
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
233+
处理节点;
234+
backtracking(路径，选择列表); // 递归
235235
回溯，撤销处理结果
236236
}
237237
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp