# My O((n-k)*k) algorithm with O(n-k) space.

• DP solution is simple, how can we get combine(n, k)? It's two parts, one part is all the elements without number n(combine(n - 1, k), and another part is all the elements with number n (append n to every element of combine(n - 1, k - 1)). We can use a two dimension array to do it. Its row number is k, column number is n. So array[i, j] stand for combine(j, i). Actually, to get combine(n, k), we only need some elements in the array, because all element array[i, j] = empty when i > i. and combine(n, k) only need combine(n - 1, k - 1). So the area we need is a parallelogram.

``````public class Solution
{
public List<List<Integer>> combine(int n, int k)
{
List<List<Integer>> result = new ArrayList<>();

if (k <= n)
{
List<List<Integer>>[] previous = (List<List<Integer>>[]) new List[n - k + 2];
List<List<Integer>>[] current = (List<List<Integer>>[]) new List[n - k + 2];

// First row is combine(n, 0). every element is empty.
for (int i = 0; i < previous.length; ++i)
{
previous[i] = Collections.singletonList(Collections.<Integer>emptyList());
}

for (int i = 1; i <= k; ++i)
{
// This one is combine(k - 1, k), it doesn't have any solution, so a empty list.
current[0] = Collections.<List<Integer>>emptyList();

for (int j = 1; j < current.length; ++j)
{
// One part of combine(k, i) is combine(k - 1, i), don't use the new element k.
current[j] = new ArrayList<>(current[j - 1]);

// Other part of combine(k, i) is with new element k, so it's every element of  combine(k - 1, i - 1) append k.
for (final List<Integer> list : previous[j])
{
final List<Integer> item = new ArrayList<>(list);
}
}
final List<List<Integer>>[] temp = previous;
previous = current;
current = previous;
}

result = previous[previous.length - 1];
}

return result;
}
}``````

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