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

combine.cc

class Solution {
public:
    void comb(int start, int idx, int k, int n, vector<int> & sol, vector<vector<int> > & res)
    {
        if(idx == k)
        {
            res.push_back(sol);
        }else
        {
            for(int i = start; i<n; ++i) // never look before is a way to avoid duplicates
            {
                sol.push_back(i+1);
                comb(i+1, idx+1, k, n, sol, res); // never look before means starting from selected next
                sol.pop_back(); // cancel result
            }
        }
    }
    
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > res;
        if(k>n || n == 0)
            return res;
        vector<int> sol;
        comb(0, 0, k, n, sol, res);
        return res;
    }
};