算法训练营第二十二天（8.4）

LeeCode77. Combinations

题目地址：力扣

题目类型：回溯、组合（不用排序）

class Solution {
private:
    vector<vector<int>> ans;
    // start代表开始的位置，k代表还需要的元素数量
    void DFS(vector<int>& path, int start,int n, int k) {
        if (k == 0) {
            ans.emplace_back(path);
            return ;
        }
        // 剪枝
        if (n - start + 1 < k) return ;
        for (int i = start; i <= n; ++i) {
            path.emplace_back(i);
            DFS(path, i + 1, n, k - 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        DFS(path, 1, n, k);
        return ans;
    }

};