/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 */

// @lc code=start
class Solution {
    vector<int> track;
    vector<vector<int>> res;

    void backtrack(int start, int n, int k) {
        if (k == track.size()) {
            res.emplace_back(track);
            return;
        }

        for (int i = start; i <= n; ++i) {
            track.emplace_back(i);
            backtrack(i + 1, n, k);
            track.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }
};
// @lc code=end