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], ] http://leetcode.com/onlinejudge#question_77

leetcode_combinations.cpp

void dfs(int n, int k, int kth, vector<vector<int> >& ret, vector<int>& cur) {
    if (k == cur.size()) {
        ret.push_back(cur);
        return;
    }
    if (kth == n + 1)
        return;
    if (k - cur.size() > n - kth + 1)
        return;
    dfs(n, k, kth + 1, ret, cur);
    cur.push_back(kth);
    dfs(n, k, kth + 1, ret, cur);
    cur.pop_back();
}

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > ret;
        vector<int> cur;
        dfs(n, k, 1, ret, cur);
        return ret;
    }
};