# My java AC solution, O(k*C(n,k)) time and O(k) space?

• The idea was, all combinations of C(n,k) is ordered. nextCombination method helps to find the next combination of the current.

For example, C(5,3) is ordered as: ((1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5), null). nextCombination(5,(1,3,4)) gives (1,3,5).

And C(4,3) is ordered as ((1,2,3), (1,2,4), (1,3,4), (2,3,4), null), nextCombination(4,(1,3,4)) gives (2,3,4).

I know the worst time complexity of nextCombination is O(k), but what about the average case? Could it be O(1) or O(logk)?

``````public class Solution {
public List<List<Integer>> combine(int n, int k){
List<Integer> comb = new LinkedList<>();
List<List<Integer>> output = new LinkedList<>();
if(k<=n){
for(int i=0;i<k;i+=1){  // initialize comb with (1,2,3...k)
}
while(comb!=null){
comb = nextCombination(n,comb);
}
}
return output;
}

public List<Integer> nextCombination(int n, List<Integer> comb){
int k = comb.size();
for(int i=k-1;i>=0;i-=1){
if(comb.get(i)<=n-k+i){
comb.set(i,comb.get(i)+1);
for(int j=i+1;j<k;j+=1){
comb.set(j,comb.get(j-1)+1);
}
return comb;
}
}// At this point, if nothing is returned, the input comb must be (n-k+1,n-k+2,...,n)
return null;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.