77. Combinations

题目链接

https://leetcode.com/problems/combinations/

解题思路

dfs

代码

class Solution {
public:
    void dfs(vector<vector<int>> &v, vector<int> &nums, vector<int> &t, int pos, int k) {
        if (k == 0) {
            v.push_back(t);
            return;
        }

        int e = nums.size() - k;
        for (int i = pos; i <= e; ++i) {
            t.push_back(nums[i]);
            dfs(v, nums, t, i + 1, k - 1);
            t.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        if (k <= 0) {
            return ans;
        }
        vector<int> nums;
        for (int i = 1; i <= n; ++i) {
            nums.push_back(i);
        }
        vector<int> t;
        dfs(ans, nums, t, 0, k);
        return ans;
    }
};