l**********1
发帖数: 415 | 1 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],
]
the given api is
public ArrayList> combine(int n, int k)
the solution I got is as follows which is really slow O(n!) and time out at
10,7. So please provide any idea of higher efficiency algorithm for this
one. Thanks in advance
public void combination(ArrayList> result,ArrayList<
Integer> subset,int n, int k){
if(k>n) return;
if(k==0){
Collections.sort(subset);
if(!result.contains(subset))
result.add(subset);
return;
}
for(int i=1;i<=n;i++){
ArrayList newset=new ArrayList();
newset.addAll(subset);
if(!newset.contains(i)){
newset.add(i);
combination(result,newset,n,k-1);
}
}
} |
|
