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

tag: backtracking

回溯问题，用递归求解就好。

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<int> thisRe;
        vector<vector<int>> re;
        if(n < 1 || k == 0 || k > n){//判断初始条件
            return re;
        }
        _combine(1, n, k, re, thisRe);
        return re;
    }
    void _combine(int start, int n, int k, vector<vector<int>> &re, vector<int> &thisRe){
        if(k == 0){//finish
            re.push_back(thisRe);
            return ;
        }
        if(n - start + 1 < k){// not enough element left
            return ;
        }
        //push start in the result
        thisRe.push_back(start++);
        k--;
        _combine(start, n, k, re, thisRe);
        
        //don't push start in the result
        thisRe.pop_back();
        k++;
        _combine(start, n, k, re, thisRe);
    }
};