从循环中调用具有指数复杂度的递归代码

Question

此代码作为 MIT programming course 中指数复杂度的示例提供：

def genSubsets(L):

    if len(L) == 0:
        return [[]] #list of empty set
    smaller = genSubsets(L[:-1]) #all subsets without last element
    extra = L[-1:] #create a list of just the last element
    new = []
    for small in smaller:
        new.append(small+extra) #for all smaller solutions, add one with last element
    return smaller+new #combine those with last element and those without

如果我使用常规列表调用 genSubsets，我会得到预期的答案（一组所有可能的子集）。

print(genSubsets([0,1,2]))
#prints - [[], [0], [1], [0, 1], [2], [0, 2], [1, 2], [0, 1, 2]]

但是，如果我尝试从循环中调用它（使用列表理解或通过使用子循环构建列表），然后调用 genSubsets，该函数无法 return预期答案。

for i in range(4):
    L = []
    for j in range(i):
        L.append(j)
    #print(L) # works as expected
    print(genSubsets([L])) # produces lists of length two regardless of number input list length

我想从循环内调用该函数，因为我很好奇 returned 子集列表的大小（即长度）如何随着输入大小的增长而增长并体验处理时间如何随着输入列表大小的增加而增加。

Answer 1

好吧，你给它一个只有一个元素的列表，所以你当然只能得到两个子集。将 genSubsets([L]) 更改为 genSubsets(L)。

从循环中调用具有指数复杂度的递归代码

Calling on recursive code with exponential complexity from a loop

python

recursion

big-o