题目：

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

思路：

递归

package recursion;import java.util.ArrayList;import java.util.List;public class Combinations {    public List
     
      
       > combine(int n, int k) {        List
       
        
         > res = new ArrayList
         
          
           >(); List
           
             record = new ArrayList
            
             (); generateRecord(res, record, 1, n, k); return res; } private void generateRecord(List
             
              
               > res, List
               
                 record, int start, int end, int k) { if (k == 0) { res.add(record); return; } for (int i = start; i <= end - k + 1; ++i) { List
                
                  newRecord = new ArrayList
                 
                  (record); newRecord.add(i); generateRecord(res, newRecord, i + 1, end, k - 1); } } public static void main(String[] args) { // TODO Auto-generated method stub Combinations c = new Combinations(); List
                  
                   
                    > res = c.combine(4, 2); for (List
                    
                      l : res) { for (int i : l) System.out.print(i + "\t"); System.out.println(); } }}