解释了Python中此递归问题的说明

Question

检查此示例代码是否进行回溯，有两种方法可以将变量i附加到curr之前，在回溯之前，此处（未注释）更新全局ANS 数组，而另一种方式没有（如下所示）。

n = 4
k = 2
ans = []
def backtrack(first, curr):
    if len(curr)==k:
        ans.append(curr)
    for i in range(first, n+1):
        # curr.append(i)
        backtrack(i+1, curr+[i])
        # curr.pop()

curr = []
backtrack(1, curr)
print("result = ",ans)

]，[2，4]，[3，4]]

另一种方式：

n = 4
k = 2
ans = []
def backtrack(first, curr):
    if len(curr)==k:
        ans.append(curr)
    for i in range(first, n+1):
        curr.append(i)
        backtrack(i+1, curr)
        curr.pop()

curr = []
backtrack(1, curr)
print("result = ",ans)

在此处输出：result = [[]，[]，[]，[]，[]，[]，[]，[]，[]]

我想理解，这里到底发生了什么变化以及为什么全局输出阵列ans行为不同

Answer 1

Curr+[I]创建一个新对象，该对象将传递给下一个递归调用。因此，每当您将Curr>附加到ANS的情况稍后修改。

当您使用.append和.pop时，您一直通过一个对象，因此，当您将其附加到ANS时，它是实际上，您一次又一次地附加的那个独特的对象。然后，您将继续更新该唯一对象，该对象将反映ans的所有元素，因为它们是同一对象。处理Curr在清除处理时给出您最终只有空的列表，即使在每个步骤Curr实际上都具有您想要的值。

您可以看到，首先添加此打印件以检查除此错误外，在这两种情况下，一切仍然与您期望的情况相同：

def backtrack(first, curr):
    print(first, id(curr), curr)
    # ... and the rest

要修复第二版，您可以通过副本传递：

curr.append(i)
backtrack(i+1, curr.copy())
curr.pop()

或当您附加到<<时复制代码> ans

ans.append(curr.copy())