Return 递归子集 - Python

Question

I have to implement a recursive function which recieves only two arguments: 'n' and 'k', where n is the length of a set of from '0' to 'n-1' and k is the length of the subsets of different elements from the original set. We have to return finally a list of lists which contains these all sub-lists in k-length. The twist here that I don't know to overcome is we mustn't use other arguments such as lists, tuples, sets, etc...

所以我不知道如何 "save" 在没有 "lost" 详细信息的情况下递归所有子集的列表。

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

我想到了类似的东西，但它总是 returns 一个空列表... 所以我想我需要了解如何在递归中一致地保存数据结构。

谢谢。

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)]

Return 递归子集 - Python

Return subsets in recursion - Python

recursion

subset

combinatorics

python-3.x