Combinations

Combinations

 Total Accepted: 36487 Total Submissions: 119636My Submissions

Question Solution 

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

思路:

针对每一个数字都作为第一个进行遍历，然后向后遍历下一个可能有，也有可能没有的。

 public List> combine(int n, int k) {
 List> result=new ArrayList();
 if(n<=0&&k<=0&&k>n)

//返回空的链表也不要返回null
 return Collections.emptyList();
 for(int e=1;e<=n;e++){
 List element=new ArrayList();
 element.add(e);
 recurTraverse(n,k-1,e+1,result,element);
  
 }
 return result;
 }
 private void recurTraverse(int n, int i, int j, List> result, List element) {
 // TODO 自动生成的方法存根
 
 if(0==i){
 result.add(element);
 return;
 }
 if(j>n)
 return;

//保留当前的element值，给有这个值用
 List temp=new ArrayList(element);
 recurTraverse(n, i, j+1, result, element);
 
 temp.add(j);
 recurTraverse(n,i-1,j+1,result,temp);
 
 
 }