生成组合数是初中的知识，没有人不知道。

组合数学我觉得是最有意思的数学分支，室友应该是这方面的专家，他的纸牌问题我听都听不懂。。

不知道你们是什么感觉。我以看到组合数，立即会想到全排列。这可能是由于当时初中的时候。这两部分知识是放在一起讲的。也确实有一些联系。如何生成全排列算法课在递归的那部分讲过，写的也比較多，非常多字符串的问题我都忍不住想用全排列试一下。

那能不能用递归的方法来生成组合数呢？

答案当然是肯定的，毕竟这样的事情递归再合适只是了。

递归的关键是什么呢。如何把大规模转化成小规模，然后小规模再一层层的回溯成大规模。

单就生成组合数的问题来说。大规模和小规模是什么呢？答案是C(n,k)与C(n-1, k-1)。去掉的这个1。是在此次递归中选取的那个数。选取的这个数究竟是什么呢？注意到选择这个数的时候一定要避免后面递归时反复的选到它，因此最简单的策略就是选择当前能选的最大的那个。依据组合数的定义，这个数的值域应该是[k, n]，问题攻克了。编码的问题非常easy。

注意一点是题目要求最后是依照升序排列的，因此要做一次排序，这是不太优雅的地方，或许换一种挑数的策略，就能够省去这一步。只是我认为应该不如这样的方法简单易理解。

class Solution {

public:

    void getCombine(int n, int k, vector<int> &tpres, vector<vector<int> > &res){

        for(int i=n;i>=k;i--){

            tpres.push_back(i);

            if(k>1)

                getCombine(i-1, k-1, tpres, res);

            else{

            	vector<int> tt = tpres;

                sort(tt.begin(), tt.end());

                res.push_back(tt);

            }

            tpres.pop_back();

        }

    }

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

        vector<vector<int> > res;

        vector<int> tpres;

        getCombine(n, k, tpres, res);

        return res;

    }

};