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 另外，用next permutation里提到的方法也可以。 代码：

1     void search(int start, int n, int k, vector
     
      
        > &result, vector
       
         &tmp){ 2         if(k == 0){ 3             if(start == 0) 4                 return; 5             result.push_back(tmp); 6             return; 7         } 8  9         if(start > n || n - start + 1 < k)10             return;11         search(start+1, n, k, result, tmp);12         tmp.push_back(start);13         search(start+1, n, k-1, result, tmp);14         tmp.pop_back();15     }16     vector
        
         
           > combine(int n, int k) {17         // IMPORTANT: Please reset any member data you declared, as18         // the same Solution instance will be reused for each test case.19         vector
          
           
             > result;20 vector
            
              tmp;21 if(k == 0) 22 return result;23 search(1, n, k, result, tmp);24 return result;25 }