Combinations

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

Naive Way: A recursive method is straightforward. Need to convey current index, n, current k as parameter to recursive function. It is a DFS idea.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     dfs(new Stack<Integer>(), 1, n, k, rslt);  
     return rslt;  
   }  
   private void dfs(Stack<Integer> path, int index, int n, int k, List<List<Integer>> rslt){  
     // ending case  
     if(k==0){  
       List<Integer> list = new ArrayList<Integer>(path);  
       rslt.add(list);  
       return;  
     }  
     // recursion case  
     for(int i = index;i <= n;i++){  
       path.push(i);  
       dfs(path, i+1, n, k-1, rslt);  
       path.pop();  
     }  
   }  
 }  

An iterative method correspondingly.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Deque<List<Integer>> gross = new ArrayDeque<List<Integer>>();  
     // edge case   
     if(k==0) return rslt;  
     // initialize the rslt  
     for(int i = 1;i <= n-k+1;i++){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(i);  
       gross.offerLast(list);  
     }  
     // iteration on k  
     int ind = 1;  
     while(ind++ < k){  
       int length = gross.size();  
       for(int i = 0;i < length;i++){  
         List<Integer> list = gross.pollFirst();  
         int num = list.get(list.size()-1);  
         for(int j = num+1;j <= n;j++){  
           List<Integer> new_list = new ArrayList<Integer>(list);  
           new_list.add(j);  
           gross.offerLast(new_list);  
         }  
       }  
     }  
     // add to result  
     while(!gross.isEmpty()) rslt.add(gross.pollFirst());  
     return rslt;  
   }  
 }