回溯无法正常工作，请帮助识别问题

Question

def combination(n,k):

    combi=[]
    
    def backtrack(start,comb):
        print(comb)
        if len(comb)==k:
            combi.append(comb.copy())
            return 
            
        for i in range(start,n+1):
            # print(i)
            cur=[i]
            backtrack(i+1,comb+cur)
            comb.pop()
            print("comb after",comb)
    backtrack(1,[])
    return combi

combination(4,3)

我得到

IndexError: pop from empty list

。 当我打印梳子来识别错误时，我得到了这个：

1
[]
i is 1
2
[1]
i is 2
3
[1, 2]
i is 3
4
[1, 2, 3]
comb after [1]
i is 4
5
[1, 4]
comb after []
comb after []
i is 3
4
[3]
i is 4
5
[3, 4]
comb after []

为什么我的代码在获得

[1,2,3]

后应该只弹出 3 时却同时弹出 2 和 3。我做错了什么？

Answer 1

comb

确实是空的。您从未在其中附加任何内容。

误解可能来自于您为递归调用构建的论点：

        backtrack(i+1,comb+cur)

...但这并不会改变

comb

。这只是创建了一个 new 列表，其中又多了一个元素，并且在函数的递归执行中，该列表被分配给一个本地名称，该名称恰好也是

comb

。但这是一个不同的变量，并且仅适用于该执行。当

backtrack

返回时，您仍然拥有与执行

comb

之前相同的

comb+cur

。

结论，你不需要弹出任何东西。您用

+cur

添加的内容只会影响递归执行所看到的内容；它不会影响函数当前执行中的

comb

变量。