题⽬链接：https://leetcode-cn.com/problems/combinations/

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输⼊: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],

] 

思路

看到k=2，那我就直接可以两层for循环了

int n = 4;
for(int i = 1; i <= n; i++) {
    for(int j = i+1; j <= n; j++) {
        cout<< i << " " << j << endl;
    }
}
 

如果输入 n=100,k=3;当然可以三层循环了；但是如果k=50呢，50层for循环，啊这~就不好整了。

那么回溯法就⽤递归来 解决嵌套层数的问题。 递归来做层叠嵌套（可以理解是开k层for循环），每⼀次的递归中嵌套⼀个for循环，那么递归就可以⽤ 于解决多层嵌套循环的问题了。

我们知道回溯法可以看成一个树（上篇文章有讲）

 从上述图中可以清楚看出，n相当于深度，k相当于宽度，从根节点开始遍历，搜素子节点。

定义两个全局变量，用来存放单一，集合结果

vector<vector<int>> result; //存放结果集合
vector<int> tmp;           //存放单一结果

 那么还需定义一个startNext，因为第一层递归到了[1,2,3,4]取1，下一层[2,3,4]中取数靠的就是startNext

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // ⽤来存放符合条件单⼀结果
void backtracking(int n, int k, int startNext)

如果path数组大小等于k，就找到停止。

if (path.size() == k) {
 result.push_back(path);
 return;
}

要遍历整个数需横纵都得遍历 ，for循环是横向遍历，递归是纵向遍历

for循环每次从startNext开始遍历，然后⽤path保存取到的节点i

for(int i = startNext; i <= n; i++) {  //横向遍历
    path.push_back(i);   //处理节点
    backtracking(n, k, i+1);   //递归，纵向
    path.pop_back();    回溯，撤销处理的节点
}

可以看出backtracking（递归函数）通过不断调⽤⾃⼰⼀直往深处遍历，总会遇到叶⼦节点，遇到了叶 ⼦节点就要返回。 backtracking的下⾯部分就是回溯的操作了，撤销本次处理的结果。

优化

图中每⼀个节点（图中为矩形），就代表本层的⼀个for循环，那么每⼀层的for循环从第⼆个数开始遍 历的话，都没有意义，都是⽆效遍历

所以，可以剪枝的地⽅就在递归中每⼀层的for循环所选择的起始位置。 如果for循环选择的起始位置之后的元素个数 已经不⾜ 我们需要的元素个数了。

接下来看⼀下优化过程如下：

1. 已经选择的元素个数：path.size();

2. 还需要的元素个数为: k - path.size();

3. 在集合n中⾄多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1呢，因为包括起始位置，我们要是⼀个左闭的集合。

举个例⼦，n = 4，k = 3， ⽬前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。 从2开始搜索都是合理的，可以是组合[2, 3, 4]。

所以我们只需在for循环i<=n的地方换成n-(k-path,size())+1就欧克了

学习于代码随想录