1-liner, 3-liner, 4-liner


  • 37

    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), [[]])

  • 0
    N

    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?


  • 1

    @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?


  • 0

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


  • 1
    P

    @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


  • 0
    R
    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


Log in to reply
 

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