Tuesday, March 10, 2015

77. Combinations Leetcode Java

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],
]
Solution:
Recursion:
Base case/ terminating case:
if(k==0) ...
recursion steps:
try current number for kth level: 
comb.add(i);

recursion to next level k-1 level:  helper(n,i+1,k-1,res,comb); // using i+1 as next level start index because no duplication is allowed. Eg. [1,2] and [2,1] are treated as the duplicated pick.
Backtrack to current level, remove the current trial and prepare for next trial comb.remove(comb.size()-1);
 public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     if(n==0 || k==0) return res;  
     List<Integer> comb=new ArrayList<Integer>();  
     helper(n,1,k,res,comb);  
     return res;  
   }  
   public void helper(int n, int start, int k,List<List<Integer>> res, List<Integer> comb){  
     if(k==0){  
       List<Integer> temp=new ArrayList<Integer>(comb);  
       res.add(temp);  
       return;  
     }   
     for(int i=start;i<=n;i++){  
       comb.add(i);  
       helper(n,i+1,k-1,res,comb);  
       comb.remove(comb.size()-1);  
     }  
   }  

No comments:

Post a Comment