题目描述

原题链接：77. 组合

解题思路

组合问题是回溯法里的经典问题，分别采用两个全局变量path记录当前组合情况，res作为结果集。每次因为结果集需要去重，因此还需要再设置一个局部变量startIndex作为每次遍历的起始值，每遍历完一种情况，该值加一，传入给下一层函数遍历。

回溯法三部曲：
（1）终止条件：当path==k，即找到k个数的组合时，将其加入结果集。
（2）选择路径：从startIndex开始选择，不超过n即可，每次加一。
（3）选择列表：从startIndex至n的这几种情况。

1、回溯法

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {          // 找到k个数，加入结果集
            res.push_back(path);
            return ;
        }
        for(int i = startIndex; i <= n; i++) {      // 每次从startIndex开始选
            path.push_back(i);                      // 将该数加入path
            backtracking(n, k, i + 1);              // 向下迭代，为了保证去重，按从小到大顺序选择，让下一次起始位置加一
            path.pop_back();                        // 回退
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);                      // 从1开始组合
        return res;
    }
};

2、剪枝优化

由于已经规定按从小到大的顺序选择数，因此若出现下图情况，其实可以在后续进行剪枝操作。

因为n = 4, k = 2，所以在1,2,3,4这四个数的选择中，当已经选择1,2,3,4之后，由于要保证结果集里不重复，因此就一定不会再有1,3,2,4这种情况。

因此，可利用从小到大的顺序遍历、startIndex控制遍历下界、n - (k - path.size())控制遍历上界，从而实现剪枝的过程。
其中，path.size()：表示当前已存入的数，k - path.size()：表示当前还可以再存几个数，n - (k - path.size()) + 1：表示当前最大的遍历起始位置。

例如：n = 4, k = 2，当path.size() = 0时，最大的起始遍历位置为n - (k - path.size()) + 1 = 4 - (2 - 0) + 1 = 3，此时可分别从1,2,3开始往后遍历。因此，不会再去遍历4，从而实现剪枝。
当path.size() = 1时，最大的起始遍历位置为n - (k - path.size()) + 1 = 4 - (2 - 1) + 1 = 4，而之前可能已经存入1,2,3，此时的起始位置范围一定为2—4，可遍历的数便为2,3,4。

注：之所加一，是因为n和(k - path.size())分别表示个数，而元素下标是从0开始，因此上述二者相减后需要再加一。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(int n, int k, int startIndex) {
        if(path.size() == k) {
            res.push_back(path);
            return ;
        }
        // n - (k - path.size())控制遍历上界，startIndex控制遍历下界
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
};

参考文章：77.组合优化