Combinations (C++ code)

LeetCode Combinations, Apr 18 '12
 难度3，出现频率4

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

思路： 每个数有两种情况：用或者不用， do it iteratively. 

void findelem(vector<vector<int> > &res, vector<int> &elem, int curdigit, int n, int k){

    if(k == 0){

       res.push_back(elem);

       return; 

    }

    for(int i = curdigit; i < n; i++){

       elem.push_back(i+1);

       findelem(res,elem,i+1,n,k-1); 

       elem.pop_back();

    }

} 

vector<vector<int> > combine(int n, int k) {

       
        vector<vector<int> > res;

        if(k > n) return res; 

        vector<int> elem;

        findelem(res, elem, 0, n, k);
 

        return res;
    }