[LeetCode] 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],
]

This is solution is not efficient, but interesting.

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        if(n == 1)
        {
            res.push_back(vector<int>({1}));
            return res;
        }
        if(k == 1) n++;
        for(int i=1;i<n;i++)
        {
            res.push_back(vector<int>({i}));   
        }
        for(int j=1;j<k;j++)
        {
            int size = res.size();
            for(int i=0;i<size;i++)
            {
                for(int w=res[i][j-1]+1;w<=n;w++)
                {
                    res.push_back(res[i]);
                    res[res.size()-1].push_back(w);
                }
            }
            res.erase(res.begin(), res.begin() + size);
        }
        return res;
    }
};

Backtracing

class Solution {
public:
    vector<vector<int> > combine(int n, int k)
    {
        vector<vector<int>> res;
        vector<int> vec;
        generate(1, n,k,res,vec);
        return res;
    }

    void generate(int start, int n, int k, 
            vector<vector<int>>& res, vector<int>& vec) 
    {
        if(k==0)
        {
            res.push_back(vec);
            return;
        } 
        for(int i=start;i<=n;i++) 
        {
            vec.push_back(i);
            generate(i+1,n,k-1,res,vec);
            vec.pop_back();
        }
    }
};