Leetcode 77: combination

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

很明显的DFS的题目：

画出DFS树，很容易找到规律做出来，这一题很类似于permutation 方法一，即一个位置一个位置设置数字，但是

这个题目里面往solu里面添加数字是有条件的： 下一层添加的数必须比上一层的树大，为了记录上一层

的数添加的是什么，在DFS 递归中引入一个新变量pre, 用来记录上一层的值。  

class Solution {
private:
    void DFS(vector<int> solu, vector<vector<int>> &rst, int n, int k, int cur, int pre) {
        if (cur == k) {
            rst.push_back(solu);
            return;
        }
        for (int i = pre  + 1; i <= n; i++) {
            solu.push_back(i);
            DFS(solu, rst, n, k, cur+1, i);
            solu.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> solu;
        vector<vector<int>> rst;
        DFS(solu, rst, n, k, 0,0);
        return rst;
    }
};