这道题当然可以用for循环嵌套解决，但是嵌套层数要根据k变化，很难写，所以还是用回溯。
回溯的核心就是for循环横向展开，然后递归纵向展开，例如n=4， k=2，一开始的集合是[1,2,3,4]，然后for循环依次取1,2,3,4，取了之后就递归继续分解。
图片来源：代码随想录。
回溯回来的时候一定要消除递归的影响，即把改变了的值改回来。
class Solution {
private:
vector path;
vector> result;
void backtracking(int n, int k, int position) {
if (path.size() == k)
result.push_back(path);
for (int i = position; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
剪枝优化：
回溯一般可以剪枝，剪枝在递归的前面进行，判断要不要进入递归，这里的剪枝方法是判断剩下的数字够不够用了。k-path.size()是还需要的数字个数，n-i+1是仍有的数字个数，若前者大于后者直接break即可。
class Solution {
private:
vector path;
vector> result;
void backtracking(int n, int k, int position) {
if (path.size() == k)
result.push_back(path);
for (int i = position; i <= n; i++) {
if ((k - path.size() > (n - i + 1)))
break;
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};
