python实现leetcode之77. 组合

解题思路

分两种情况
1.从前面n-1个元素里取k个，一共有first_half种组合
2.从前面n-1个元素里取k-1个，再在每种方案上加上最后一个元素last，一共有second_half种组合
两种组合一起就是结果

77. 组合

代码

class Solution:
    def combine(self, n: int, k: int):
        if k > n: return []
        return combine(list(range(1, n+1)), k)


def combine(li, k):
    if k > len(li): return []
    if k == 1: return [[i] for i in li]
    *rest, last = li
    # 不包含最后一个: 从前面取k个
    first_half = combine(rest, k)
    # 包含最后一个: 从前面取k-1个,然后在追加最后一个
    second_half = [[*arr, last] for arr in combine(rest, k-1)]
    return [*first_half, *second_half]