Simple java solution, generate comb from a bigger number


  • 2
    T
    public List<List<Integer>> combine(int n, int k) {
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
        result.add(new LinkedList<Integer>());
        for (int j = k - 1; j >= 0; j--) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                LinkedList<Integer> res = (LinkedList<Integer>) result.pollFirst();
                int start = (res.isEmpty()) ? 0 : res.getLast();
                for (int m = start + 1; m + j <= n; m++) {
                    List<Integer> r = new LinkedList<Integer>(res);
                    r.add(m);
                    result.add(r);
                }
            }
        }
        return result;
    }
    

    for combine(4, 2)

    we generate(1,), (2,), (3,)

    then (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)

    we generate every level from start+1 to n-j

    for the number bigger than n-j, it is impossible to find a bigger number to complete the comb


Log in to reply
 

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