使用幂集示例理解递归

Question

我写了一段简单的代码，使用递归打印集合的所有子集。我很难理解输出。例如，输出中的第一行显示了一个空集和一个3的单例，而我希望打印一个空集合和一个1的单例然后是空集、一个1、一个2等。然而，打印的不是这样。我不知道如何可视化递归树。是否有实现可视化的通用技术？我试着画一棵树，但很快就弄糊涂了。

def subsets(self, nums):
inp = nums
out = []
result=[]
def helper(inp,out,index):
if index==len(inp):
result.append(out)
return
helper(inp,out,index+1)
helper(inp,out+[inp[index]],index+1)
print(result)
helper(inp,out,0)
return result

输入"[1，2，3]"的打印语句输出显示在下方

[[], [3]]
[[], [3], [2], [2, 3]]
[[], [3], [2], [2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Answer 1

如果添加一个"压痕"；参数，当您探索它时，您可以立即看到哪个函数调用哪个：

def subsets(nums):
inp = nums
out = []
result=[]
def helper(indent,inp,out,index):
print(f"{indent}->helper({inp},{out},{index})")
if index==len(inp):
result.append(out)
return
helper(indent+'--',inp,out,index+1)
helper(indent+'--',inp,out+[inp[index]],index+1)
helper('',inp,out,0)
return result

结果看起来像：

->helper([1, 2, 3],[],0)
--->helper([1, 2, 3],[],1)
----->helper([1, 2, 3],[],2)
------->helper([1, 2, 3],[],3)
------->helper([1, 2, 3],[3],3)
----->helper([1, 2, 3],[2],2)
------->helper([1, 2, 3],[2],3)
------->helper([1, 2, 3],[2, 3],3)
--->helper([1, 2, 3],[1],1)
----->helper([1, 2, 3],[1],2)
------->helper([1, 2, 3],[1],3)
------->helper([1, 2, 3],[1, 3],3)
----->helper([1, 2, 3],[1, 2],2)
------->helper([1, 2, 3],[1, 2],3)
------->helper([1, 2, 3],[1, 2, 3],3)

因此，你可以立即看到为什么你首先得到[]——当你一路浏览列表而不在结果中包含任何内容时，你就会得到它。你得到[3]下一个，因为你回溯到你加3的调用，然后走到最后。通过进一步回溯到输出中包含2的位置，然后沿着不添加3的路径前进，可以得到[2]。然后你得到[2,3]，因为你回溯了一个级别，到结果中包含2的调用，这次转到添加3的路径。

不过，这可能不是计算幂集的最简单方法。大小为n的幂集与0和2*n-1之间的二进制数之间存在一一对应关系。对于每个数字，1位表示要包含在集合中的元素。所以你也可以这样计算功率集：

def subsets(nums):
return [
[nums[j] for j, b in enumerate(reversed(format(i, 'b'))) if b == '1']
for i in range(2**len(nums))
]

它以指数大小运行，但递归版本也是如此，当输出是输入大小的指数时，这是不可避免的。