题解 | #牛棚分组# 回溯

知识点

回溯

思路

数据范围很小，可以考虑回溯的方法。从1开始向n搜索，直到待选个数为0或者已经超出范围时停止，同时维护路径，如果满足条件则将当前路径加入答案中。因为要求字典序，所以我们优先选择保留当前数字的路径。

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> res;
        function<void(vector<int>&, int, int)> dfs = [&](vector<int>& path, int x, int u) {
            if (u == 0 or x > n) {
                if (x <= n + 1 and u == 0) {
                    res.push_back(path);
                }
                return;
            }
            path.push_back(x);
            dfs(path, x + 1, u - 1);
            path.pop_back();
            dfs(path, x + 1, u);
        };
        vector<int> p;
        dfs(p, 1, k);
        return res;
    }
};