题解 | #牛棚分组#

考察知识点：回溯

题目分析：

因为答案是按照升序排序，并且是组合方案，那么分组中的第一个数就是1 ~ n - k + 1。以此作为递归的入口，我们只需要看能够与后面几个数一起组合成k个数即可。当group内放入了k个数，说明找到了一组，将其加入结果中即可。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型vector<vector<>>
     */
    void dfs(int n, int k, int start, vector<int> &group, vector<vector<int>> &res) {
        int size = group.size();
        if (size == k) {
            res.push_back(group);
            return;
        }
        for (int i = start; i <= n; i++) {
            group.push_back(i);
            dfs(n, k, i + 1, group, res);
            group.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        // write code here
        vector<vector<int>> res;
        vector<int> group;
        for (int i = 1; i <= n - k + 1; i++) {
            group.push_back(i);
            dfs(n, k, i + 1, group, res);
            group.pop_back();
        }
        return res;
    }
};