# 1-liner, 3-liner, 4-liner

• Library - AC in 64 ms

First the obvious solution - Python already provides this functionality and it's not forbidden, so let's take advantage of it.

``````from itertools import combinations

class Solution:
def combine(self, n, k):
return list(combinations(range(1, n+1), k))
``````

Recursive - AC in 76 ms

But doing it yourself is more interesting, and not that hard. Here's a recursive version.

``````class Solution:
def combine(self, n, k):
if k == 0:
return [[]]
return [pre + [i] for i in range(1, n+1) for pre in self.combine(i-1, k-1)]
``````

Iterative - AC in 76 ms

And here's an iterative one.

``````class Solution:
def combine(self, n, k):
combs = [[]]
for _ in range(k):
combs = [[i] + c for c in combs for i in range(1, c[0] if c else n+1)]
return combs
``````

Reduce - AC in 76 ms

Same as that iterative one, but using `reduce` instead of a loop:

``````class Solution:
def combine(self, n, k):
return reduce(lambda C, _: [[i]+c for c in C for i in range(1, c[0] if c else n+1)],
range(k), [[]])``````

• class Solution:
def combine(self, n, k):
if k == 0:
return [[]]
return [pre + [i] for i in range(1, n+1) for pre in self.combine(i-1, k-1)]
how it works?

• @StefanPochmann Hi Stefan, I've learned a lot from your solutions. But the 'Recursive', 'Iterative' and 'Reduce' solutions all get `Time Limit Exceeded`. Did you find it out?

• @J.R.Smith Yeah that's because a larger test case was recently added, making those solutions a little too slow.

• @J.R.Smith

This could be solved by adding one more constraint:

``````if  n < k:
return []
``````

I tested this on the 3-liner version and got accepted

• ``````if n-k == 0:
return [list(range(1, n+1))]
ret = [[]]
for i in range(min(k, n-k)):
ret = [choose+[j] for choose in ret for j in range(choose[-1]+1 if choose else 1, n+1)]
if n-k < k:
ret = [[y for y in range(1, n+1) if y not in x] for x in ret]
return ret
``````

A more efficient version based on the same iterative logic

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