leetcode 77. Combinations-蒲公英云

leetcode 77. Combinations

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
class Solution {
    void choose_one(vector<pair<vector<int>, vector<int>>>&candi)
    {
        vector<pair<vector<int>, vector<int>>>newcandi;
        for (int i = 0; i < candi.size(); i++)
        {
            for (int j = 0; j < candi[i].second.size(); j++)
            {
                vector<int>bb = candi[i].first;
                bb.push_back(candi[i].second[j]);
                vector<int>cc = candi[i].second;
                cc.erase(cc.begin(), cc.begin() + j + 1);
                newcandi.push_back(pair<vector<int>, vector<int>>(bb, cc));
            }
        }
        candi = newcandi;
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>>re;
        vector<int>aa;
        if (k == 0)
        {
            re.push_back(aa);
            return re;
        }
        vector<int>nums;
        for (int i = 0; i < n; i++)
            nums.push_back(i + 1);
        vector<pair<vector<int>, vector<int>>>candi;
        candi.push_back(pair<vector<int>, vector<int>>(aa, nums));
        int kk = 0;
        while (kk < k)
        {
            choose_one(candi);
            kk++;
        }
        for (int i = 0; i < candi.size(); i++)
            re.push_back(candi[i].first);
        return re;
    }
};