给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]示例 2：
输入：n = 1, k = 1
输出：[[1]]提示：
1 <= n <= 201 <= k <= n
解题思路：回溯
这道题直接用暴力的话会发现是超时，但是时间复杂度其实是非常高的，我们需要套 k 层 for 循环！
所以这种组合的问题就很适合用回溯来解决，特别是当其是组合，而不是排列的时候！
把组合问题抽象为如下树形结构：
接下来就是回溯三部曲：
- 确定递归函数的返回值以及参数
- 因为我们最后要返回一个
vector<vector<int>>，那么期间我们也得有一个vector<int>来记录当前符合条件的结果 - 除此之外，为了防止出现重复的组合，我们需要一个
curindex变量，比如这次是[1, 2, 3]中取 1，那么下一层递归中就要从 2 开始取，不然就会出现 11 的情况！所以需要curindex来记录下一层递归，搜索的起始位置。
- 因为我们最后要返回一个
- 回溯函数终止条件
- 通过这道题我们很清楚的知道终止条件就是要判断这个最后结果的位数也就是
k，那么我们只需要判断v数组中的长度是否等于k，等于说明已经满足了，就不需要再向下递归了，则将当前的结果集放到vv中，然后return。
- 通过这道题我们很清楚的知道终止条件就是要判断这个最后结果的位数也就是
- 单层搜索的过程
- 回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出
for循环用来横向遍历，而递归的过程是纵向遍历。
- 如此我们才遍历完图中的这棵树。
for循环每次从curindex开始遍历，然后用v保存取到的节点 i。 - 并且不要忘记在途中递归向下取下一个数字的时候，返回之后，我们还需要继续一个回溯，也就是将
v中刚才递归下去的那层的那个i去掉，这是为了防止我们取不到下下个数字，比如说[1, 2, 3]，我们现在取了 1，并且先继续插入到v中，然后我们递归到下一层取了[1, 2]，此时 2 也会被push到v中，那么返回回来的时候如果不将 2pop掉的话，v就还是k = 2，那么递归下一层的时候就直接返回了，就取不到[1, 3]了！
- 回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出
class Solution {
public:
void backtracking(int n, int k, int curindex)
{
if(v.size() == k)
{
vv.push_back(v);
return;
}
for(int i = curindex; i <= n; ++i)
{
v.push_back(i); // 处理当前节点
backtracking(n, k, i + 1); // 递归到下一层取下一个数
// 回溯，才能接下去判断后面数字
v.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return vv;
}
private:
vector<int> v; // 用来存放符合条件结果
vector<vector<int>> vv; // 存放符合条件结果的集合
};剪枝优化
我们说过，回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。
在遍历的过程中有如下代码：
for(int i = curindex; i <= n; ++i)
{
v.push_back(i);
backtracking(n, k, i + 1);
v.pop_back();
} 这个遍历的范围是可以剪枝优化的，怎么优化呢？
来举一个例子，n = 4，k = 4的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。 在第二层 for 循环，从元素 3 开始的遍历都没有意义了。
这么说有点抽象，如图所示：
图中每一个节点（图中为矩形），就代表本层的一个 for 循环，那么每一层的 for 循环从第二个数开始遍历的话，都没有意义，都是无效遍历。为什么呢❓❓❓
因为我们要的 k 是 4，但是从 2 开始的话，就算加上 3 和 4，最多就是 3 个数，不可能到达 k = 4 的个数，所以就是无效遍历！所以，可以剪枝的地方就在递归中每一层的 for 循环所选择的起始位置。
也就是说，如果 for 循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
注意代码中 i，就是 for 循环里选择的起始位置。
for(int i = curindex; i <= n; ++i)接下来看一下优化过程如下：
- 已经选择的元素个数：
v.size() - 还所需的元素个数为:
k - v.size() - 因为 列表中剩余元素（
n-i）≥ 还所需的元素个数（k - v.size()） 才有意义要遍历下去！ - 所以最后得到：
i ≤ n - (k - v.size()) + 1
为什么有个+1呢❓❓❓因为包括起始位置，我们要是一个左闭的集合。
举个例子，n = 4，k = 3， 目前已经选取的元素为 0，即 v.size() 为 0，则 n - (k - 0) + 1 即 4 - (3 - 0) + 1 = 2。
从 2 开始搜索都是合理的，可以是组合 [2, 3, 4]。
这里大家想不懂的话，建议也举一个例子，就知道是不是要+1了。
所以优化之后的 for 循环是：
for(int i = curindex; i <= n - ( k - v.size() ) + 1; ++i) // 剪枝优化 优化后整体代码如下：
class Solution {
public:
void backtracking(int n, int k, int curindex)
{
if(v.size() == k)
{
vv.push_back(v);
return;
}
for(int i = curindex; i <= n-(k-v.size())+1; ++i) // 剪枝优化
{
v.push_back(i);
backtracking(n, k, i + 1);
v.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return vv;
}
private:
vector<int> v;
vector<vector<int>> vv;
};