使用递归查找所有 k 个子集

Question

我正在尝试找到一种方法来创建一个递归算法，该算法将给出一组数字 (0 -> n) 的所有 k 长度子集，但我无法将列表作为参数发送给函数。最终我想返回一个列表列表我想从最后开始，使用某种DP。我尝试过的所有东西都没有接近它

Answer 1

首先处理最后一个元素 ( n-1) 允许您不使用给定的函数签名传递中间结果：

def subsets(n, k):

    if n < k or k < 0:

        return []

    if k == n:

        return [list(range(k))]

    return subsets(n-1, k) + [s+[n-1] for s in subsets(n-1, k-1)]

>>> subsets(3, 2)

[[0, 1], [0, 2], [1, 2]]

>>> subsets(4, 2)

[[0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]]

>>> subsets(4, 3)

[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]]