创建大小为 k 的列表的组合时出现回溯问题

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。为什么它不只弹出 3。我做错了什么？

Answer 1

comb

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

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

        backtrack(i+1,comb+cur)

...但这并不会改变

comb

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

comb

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

backtrack

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

comb

之前相同的

comb+cur

。

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

+cur

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

comb

变量。

替代方案

您可以将其与调用

pop()

有意义的代码版本进行比较：

    comb.append(i)  # Now we DO mutate `comb` here
    backtrack(i+1,comb)
    comb.pop()  # ... and need to revert that change.

Answer 2

当您使用comb + cur时，您正在创建一个新列表。因此，当调用comb.pop()时，它会从原始梳列表中弹出。这是修复方法

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):
            comb.append(i)
            backtrack(i + 1, comb)
            comb.pop()
            # print(f"comb after: {comb}")
    
    backtrack(1, [])
    return combi

print(combination(4, 3))