2015年9月28日星期一

Leetcode 77 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],
]
Solution 1: pay attention this is combination(组合) not permutation(排列).
 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<Integer> one=new ArrayList<>();  
     List<List<Integer>> res=new ArrayList<>();  
     dfs(1,k,n,one,res);  
     return res;  
   }  
   private void dfs(int i, int k, int n, List<Integer> one, List<List<Integer>> res) {  
     if (k==one.size()) res.add(new ArrayList<Integer>(one));  
     else if (i>n) return;  
     else {  
       for (int j=i; j<=n; j++) {  
         one.add(j);  
         dfs(j+1,k,n,one,res);  
         one.remove(one.size()-1);  
       }  
     }  
   }  
 }  

没有评论:

发表评论