回溯生成k长度列表组合时遇IndexError问题排查

你的代码尝试用回溯法生成1到n中长度为k的组合，但运行时触发IndexError: pop from empty list，且执行过程中的弹出行为不符合预期，问题出在回溯逻辑的错配上：

先看你的原代码：

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):
            cur=[i]
            backtrack(i+1,comb+cur)
            comb.pop()
            print("comb after",comb)
    backtrack(1,[])
    return combi

combination(4,3)

错误原因 #

你混淆了两种回溯实现方式：

1. 当你调用backtrack(i+1, comb+cur)时，comb+cur会创建一个全新的列表，原comb完全没有被修改。
2. 但你紧接着调用comb.pop()，试图修改原comb——可原comb根本没添加过元素，这就导致了不必要的弹出，甚至在comb为空时触发错误。

比如生成[1,2,3]的过程：

• 原comb是[1,2]，传递给回溯函数的是新列表[1,2,3]，回溯返回后，你pop原comb，它变成[1]；
• 接下来循环到i=4，传递新列表[1,4]，返回后pop原comb，它变成[]；
• 循环结束后，又执行一次pop，此时comb为空，直接报错。

修正方案 #

有两种标准写法可以解决这个问题：

方案一：修改原列表+回溯撤销（经典回溯写法）

这种方式直接操作原列表，添加元素后回溯，返回后撤销添加：

def combination(n,k):
    combi=[]
    
    def backtrack(start,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()
    
    backtrack(1,[])
    return combi

print(combination(4,3))  # 输出 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

方案二：传递新列表（无需撤销操作）

如果坚持用创建新列表的方式，就不需要调用pop，因为原列表从未被修改：

def combination(n,k):
    combi=[]
    
    def backtrack(start,comb):
        if len(comb)==k:
            combi.append(comb)
            return 
            
        for i in range(start,n+1):
            backtrack(i+1, comb + [i])
    
    backtrack(1,[])
    return combi

print(combination(4,3))  # 输出 [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

内容的提问来源于stack exchange，提问作者data_geek