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

参考别人的code, 看似不难的题，其实有点小难的，recursive function并不好写。思想还是：From this example, we can see that in the first position of the resulting combinations we can chose number 1-5.  Assume that we chose 1 for the 1 position of the combination, then we can choose 2-5 for the second position.  Till we chosen numbers for all position, we can have one possible combination.

However, when we chose 3 for the first position and 5 for the second position, we don't have any other number to choose for the 3rd position. (former number must be smaller than the following number).

1 public class Solution { 2     public ArrayList
     
      
       > combine(int n, int k) { 3         ArrayList
       
         set = new ArrayList
        
         (); 4         ArrayList
         
          
           > sets= new ArrayList
           
            
             >(); 5 6 if (n < k) return sets; 7 helper(set, sets, 1, n, k); 8 return sets; 9 }10 11 public void helper(ArrayList
             
               set, ArrayList
              
               
                > sets, int starter, int n, int k) {12 if (set.size() == k) {13 sets.add(new ArrayList
                
                 (set));14 return;15 }16 17 else {18 19 for (int j = starter; j <= n; j++) {20 set.add(j);21 helper(set, sets, j+1, n, k);22 set.remove(set.size()-1);23 }24 }25 }26 }
                
               
              
             
            
           
          
         
        
       
      
     

sets.add(new ArrayList<Integer>(set)); 要特别注意，我写成sets.add(set)就会在以下情况报错：input为： 1,1; expected：[[1]], output: [[]]