Combinations

题目：

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example: For example, If n = 4 and k = 2, a solution is:

[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

分析：

标准的dfs解法，在这道题目中其实不需要开nums, 只需要带入个n，然后每次取数字的时候不用num[i]而是用i本身。

解法：

class Solution {
public:
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    void dfs(int n, 
                vector<int> instance, 
                vector<vector<int> >& res, 
                int start,
                int k) {

        if (instance.size() == k) {
            res.push_back(instance);
            return;
        }

        for (int i = start; i <= n; i++) {
            instance.push_back(i);
            dfs(n, instance, res, i + 1, k);
            instance.pop_back();
        }
    } 

    vector<vector<int> > combine(int n, int k) {
        // write your code here
        if (k > n) {
            vector<vector<int> >() ;
        }

        vector<vector<int> > res;
        vector<int> instance;

        dfs(n, instance, res, 1, k);
        return res;
    }
};