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

Question

我正在尝试找到一种方法来创建一个递归算法，该算法将给出一组数字 (0 -> n) 的所有 k 长度子集，但我无法将列表作为参数发送给函数。

最终我想返回一个列表列表

我想从最后开始，使用某种DP。我尝试过的所有东西都没有接近它

Answer 1

首先处理最后一个元素 ( n-1) 允许您不使用给定的函数签名传递中间结果：def subsets(n, k):&nbsp; &nbsp; if n < k or k < 0:&nbsp; &nbsp; &nbsp; &nbsp; return []&nbsp; &nbsp; if k == n:&nbsp; &nbsp; &nbsp; &nbsp; return [list(range(k))]&nbsp; &nbsp; 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]]