第77题. 组合

这题求组合大家很容易就可以想到for循环，但是两层三层for循环还好，如果是十几层几十层for循环实现起来就很麻烦了，虽然想要暴力解法，但是暴力解法也写不出来。

这时就可以使用回溯写法，回溯法就用递归来解决嵌套层数的问题。

递归来做层序遍历（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。

回溯法解决的问题都可以抽象为树形结构(N叉树),用树形结构来理解回溯就容易多了

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

可以发现n相当于树的宽度，k相当于树的深度。

那么如何在这个树上遍历，然后收集到我们想要的结果集呢？

图中每次搜索到了叶子节点，我们就找到了一个结果。

相当于只需要把达到叶子结点的结果收集起来，就可以得到n个数中k个数的组合集合。

回溯三部曲

1.确定递归返回值和参数：回溯返回值一般是void,因为需要记录下来的递归的路径，所以定义一个全局变量vector<int>path, 还有一个结果集vector<vector<int>>，其实也可以将这两个全局变量定义为引用参数，但是这样会使参数看起很冗余。参数：个数n,组合数长度k，还有需要一个int类型的参数startIndex,startIndex用于控制当前添加进组合的数字的范围，每一次添加进一个数字，下一次取数的范围都需要进行缩小，对于取过的数，后面取数也是通过startIndex进行限制不能取。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。

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

2.回溯终止条件：

如果path这个数组的大小等于k就终止

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

3.单层递归逻辑

回溯法的搜索过程就是一个树型结构的遍历过程，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

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

整体代码：

class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.push_back(i); // 处理节点 
            backtracking(n, k, i + 1); // 递归
            path.pop_back(); // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        result.clear(); // 可以不写
        path.clear();   // 可以不写
        backtracking(n, k, 1);
        return result;
    }
};

剪枝操作

可以剪枝的地方就在递归中每一层for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数已经不足我们 需要元素个数了，就没有必要搜索了。

注意代码中的i,就是for循环里选择的起始位置。

for (int i = startIndex; i <= n; i++) {

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

还需要的元素个数：k-path.size()

在集合n中至多从该起始位置：n-(k-path.size())+1开始遍历

这个表达式怎么理解？n代表集合大小，当集合中遍历所剩的元素不足以填充所需要的元素的时候，for循环就不必在进行下去了，例如：n=4 k=3 当前path.size()等于0，这时的最大起始位置是4-3+1=2，如果当前遍历到的元素大于2的时候，集合n所剩的元素不足以填充所需要的元素个数，所以循环结束。只有初始位置从小于等于2的值开始遍历才有意义。

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置