найти все k подмножеств с помощью рекурсии

Question

Я пытаюсь найти способ создать рекурсивный алгоритм, который даст все подмножества k-длины набора чисел (0 -> n), но я не могу отправить список функции в качестве аргумента.

В конце концов я хочу вернуть список списков

Я думал о том, чтобы начать с конца, используя какой-нибудь 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]]