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;
4143for (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 <=
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- < img src = ' ../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+ < img src = ' ../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- < img src = ' ../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; // 存放符合条件结果的集合
99105vector<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<img src =' ../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<img src =' ../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 }
184196public:
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