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！

1 class Solution { 2 public: 3     void getNextComb(vector
     
      
        > &res, vector
       
         v, int n, int k, int idx) { 4         if (idx > n) { 5             return; 6         } 7         v.push_back(idx); 8         if (v.size() == k) { 9             res.push_back(v);10         }11         12         getNextComb(res, v, n, k, idx + 1);13         v.pop_back();14         getNextComb(res, v, n, k, idx + 1);15     }16     17     vector
        
         
           > combine(int n, int k) {18         vector
          
           
             > res;19 vector
            
              v;20 int idx = 1;21 getNextComb(res, v, n, k, idx);22 return res;23 }24 };