a problem from leetcode: high efficiency algorithm for combinations problem# JobHunting - 待字闺中
l*1
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);
}
}
}
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
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
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.addAll(subset);
if(!newset.contains(i)){
newset.add(i);
combination(result,newset,n,k-1);
}
}
}