My AC Python code

  • 0

    It is a typical reduce-and-conquer problem.

    class Solution(object):
        def combine(self, n, k):
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            def gen_comb(nums, begin, end, k):
                generate k-length combination for nums[begin:end]
                if k == 0:
                    return [] 
                if k == 1:
                    return [[x] for x in nums[begin:end]]
                if k == end-begin:
                    return [nums[begin:end]]
                comb1 = gen_comb(nums, begin+1, end, k)
                comb2 = gen_comb(nums, begin+1, end, k-1)
                for x in comb2:
                    x.insert(0, nums[begin])
                return comb1 + comb2
            nums = [i+1 for i in range(n)]
            return gen_comb(nums, 0, n, k)

Log in to reply

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