Возврат подмножеств в рекурсии - Python

Question

Я должен реализовать рекурсивную функцию, которая получает только два аргумента: 'n' и 'k', где n - длина набора от '0' до 'n-1', а k - это длинадлина подмножеств различных элементов из исходного набора.Наконец, мы должны вернуть список списков, который содержит все эти подсписки k-длины.Вот поворот, который я не знаю, чтобы преодолеть это то, что мы не должны использовать другие аргументы, такие как списки, кортежи, множества и т. Д. ...

Так что я не знаю, как «сохранить»"в рекурсии список всех подмножеств без" потерянных "деталей.

def ret_k_subset(n, k):
    if n >= 0 and k >= 0:
        lst = []
        if len(lst) == k:
            return lst
        else:
            for n in range(n):
                return lst + ret_k_subset(n, k)
    return lst

Я думал о чем-то подобном, но он всегда возвращает пустой список ... Поэтому я думаю, что мне нужно понять, как сохранитьструктуры данных последовательно в рекурсии.

Спасибо.

Answer 1

Это может быть сделано несколькими способами, IMO, самое простое - сделать тот шаг рекурсии, который использует свойство последнего элемента (n-1) в списке результатов или нет, и с соответствующей конструкцией результата рекурсии создает свой результат.Вот реализация:

def ret_k_subset(n, k):
    if k == 0:
        return [[]]
    if k == n:
        return [list(range(n))]
    return ret_k_subset(n - 1, k) + [x + [n - 1] for x in ret_k_subset(n - 1, k - 1)]