# Iterative Java solution

• 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);
}
}
}
combs = newCombs;
}
return combs;
}
}``````

``````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);
}
}
res = tmp;
}
return res;
}``````

• 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.

• This post is deleted!

• Time out on (20, 16)

• @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]]

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