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


  • 1
    H

    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)
                    comb.add(i+1);
                }
                while(comb!=null){
                    output.add(new LinkedList(comb));
                    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;
        }
    }

Log in to reply
 

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