Iterative Java solution


  • 18
    S

    Hi guys!

    The idea is to iteratively generate combinations for all lengths from 1 to k. We start with a list of all numbers <= n as combinations for k == 1. When we have all combinations of length k-1, we can get the new ones for a length k with trying to add to each one all elements that are <= n and greater than the last element of a current combination.

    I think the code here will be much more understandable than further attempts to explain. :) See below.

    Hope it helps!


    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            if (k == 0 || n == 0 || k > n) return Collections.emptyList();
            List<List<Integer>> combs = new ArrayList<>();
            for (int i = 1; i <= n; i++) combs.add(Arrays.asList(i));
            for (int i = 2; i <= k; i++) {
                List<List<Integer>> newCombs = new ArrayList<>();
                for (int j = i; j <= n; j++) {
                    for (List<Integer> comb : combs) {
                        if (comb.get(comb.size()-1) < j) {
                            List<Integer> newComb = new ArrayList<>(comb);
                            newComb.add(j);
                            newCombs.add(newComb);
                        }
                    }
                }
                combs = newCombs;
            }
            return combs;
        }
    }

  • 11
    Q

    I like your code, it's elegant, I read your code carefully and have some optimizations for your code.

    public List<List<Integer>> combine(int n, int k) {
        if (n == 0 || k == 0 || k > n) return Collections.emptyList();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 1; i <= n + 1 - k; i++) res.add(Arrays.asList(i));
        for (int i = 2; i <= k; i++) {
            List<List<Integer>> tmp = new ArrayList<List<Integer>>();
            for (List<Integer> list : res) {
                for (int m = list.get(list.size() - 1) + 1; m <= n - (k - i); m++) {
                    List<Integer> newList = new ArrayList<Integer>(list);
                    newList.add(m);
                    tmp.add(newList);
                }
            }
            res = tmp;
        }
        return res;
    }

  • 0
    S

    Can anybody comment on the time complexity of this solution? Since the size of the combs increase drastically, I can hardly understand the time complexity.


  • 0
    R
    This post is deleted!

  • 2
    H

    Time out on (20, 16)


  • 0
    R

    @skylinebaby It should be about O(k*n).

    See below the execution for n=5 and k=4:

    initially: [[1], [2]]

    For i = 2,

    temp list: [1]
    m: from 2 to 3
    after adding elements: [[1, 2], [1, 3]]
    temp list: [2]
    m: from 3 to 3
    after adding elements: [[1, 2], [1, 3], [2, 3]]

    For i = 3,

    temp list: [1, 2]
    m: from 3 to 4
    after adding elements: [[1, 2, 3], [1, 2, 4]]
    temp list: [1, 3]
    m: from 4 to 4
    after adding elements: [[1, 2, 3], [1, 2, 4], [1, 3, 4]]
    temp list: [2, 3]
    m: from 4 to 4
    after adding elements: [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

    For i = 4,

    temp list: [1, 2, 3]
    m: from 4 to 5
    after adding elements: [[1, 2, 3, 4], [1, 2, 3, 5]]
    temp list: [1, 2, 4]
    m: from 5 to 5
    after adding elements: [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5]]
    temp list: [1, 3, 4]
    m: from 5 to 5
    after adding elements: [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5]]
    temp list: [2, 3, 4]
    m: from 5 to 5
    after adding elements: [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]


Log in to reply
 

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