Share
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

AC代码

void digui(int n, int k, int idx, vector<int>& v, vector<vector<int>>& ans) {
    if (k == 0) {
        ans.push_back(v);
        return;
    }
    for (int i = idx; i <= n; ++i) {
        if (!v.empty() && i <= v[v.size() - 1]) continue;
        v.push_back(i);
        digui(n, k - 1, idx + 1, v, ans);
        v.pop_back();
    }
}

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> v;
        digui(n, k, 1, v, ans);
        return ans;
    }
};

优化代码1（非递归）

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> out(k, 0);
        int i = 0;
        while (i >= 0) {
            ++out[i];
            if (out[i] > n) --i;
            else if (i == k - 1) res.push_back(out);
            else {
                ++i;
                out[i] = out[i - 1];
            }
        }
        return res;
    }
};

优化代码2（递归）

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if (k > n || k < 0)
            return {};
        else if (k == 0)
            return {{}};
        vector<vector<int>> res = combine(n - 1, k - 1);
        for (auto& row : res) row.push_back(n);
        for (auto& row : combine(n - 1, k)) res.push_back(row);
        return res;
    }
};

总结

自己写的递归属实有、🍔🍔。优化1和2学习自：https://www.cnblogs.com/grandyang/p/4332522.html