Combinations

Another DP problem again, but this one is not that hard. Just recursively add elements starting from 1 to n, once tmpList is size of k, then pop out latest added number, and add next one, until number "n" is met. For example, n is 5, k is 3. Firstly, 1,2,3 are added, then tmpList contains 3 elements, now 3 is removed, 4 added, again, 4 removed, 5 added. Once we meet the end, it's time to get back, and 2 is removed, 3 is added, go on over and over again. It could also be implemented by using stack. A little bit tricky part is to find out the upper limit for ith number in tmpList. Lets go back to the example n = 5, k = 3 again. For 1st element in tmpList, its range is from 1 to 3, for 2nd  one, from 2 to 4, 3rd one, from 3 to 5. The formula for upper limit is " n - (k - tmpList.size() )+ 1 ". (k - tmpList.size()) is the number of elements needed.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     if(n < k || n <= 0 || k <= 0) return null;  
     ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();  
     ArrayList<Integer> tmpList = new ArrayList<Integer>();  
     if(n == k){  
       for(int i = 1; i <=n ; i++){  
         tmpList.add(i);  
       }  
       res.add(tmpList);  
     }  
     else {  
       // tmp.add(1);  
       buildComb(n,k,res,tmpList,1);  
     }  
     return res;  
   }  
   public void buildComb(int n, int k, ArrayList<List<Integer>> res, ArrayList<Integer> tmpList, int newElem){  
     if(tmpList.size() == k){  
       ArrayList<Integer> tmpRes = new ArrayList<Integer>();  
       tmpRes.addAll(tmpList);  
       res.add(tmpRes);  
       return;  
     }  
     for(int i = newElem; i<= ( n - (k - tmpList.size() )+ 1 ) ;i++){  
       tmpList.add(i);  
       buildComb(n,k,res,tmpList,i+1);  
       tmpList.remove(tmpList.size()-1);    
     }  
   }  
 }