Python递归生成全排列时for循环不遍历空列表的问题求助

原代码核心问题 #

• 空集合判断逻辑位置错误：你将空集判断写在了for循环内部，当传入空集合时，for循环不会执行，对应的保存结果逻辑永远触发不了
• 结果追加时未做列表拷贝：Python中列表是可变对象，直接append(output)是将output的引用存入master_output，后续对output的修改会同步到所有已存入的结果中
• 遍历过程中修改原列表：你在遍历传入的列表时直接调用remove()方法，且列表传参为引用传递，会导致上层递归的列表被意外修改，同时遍历过程中修改列表会出现元素漏遍历的问题
• 变量命名不规范：使用了Python内置关键字set作为参数名，会覆盖内置的集合类型，同时全局变量master_output、output封装性极差，多次调用函数会出现结果污染

修正后的代码 #

def perm_tree(arr):
    master_output = []
    def backtrack(current_arr, path):
        # 空数组判断放在最开头，进入函数先判断是否到达终止条件
        if not current_arr:
            # 追加path的副本，避免后续修改影响已保存的结果
            master_output.append(path.copy())
            return
        # 遍历当前数组的所有元素
        for i in range(len(current_arr)):
            # 选择当前元素
            path.append(current_arr[i])
            # 生成新的数组（排除当前选中的元素），传入下一层递归，不修改原数组
            next_arr = current_arr[:i] + current_arr[i+1:]
            backtrack(next_arr, path)
            # 回溯，弹出最后添加的元素
            path.pop()
    backtrack(arr, [])
    return master_output

result = perm_tree([1, 2, 3])
print(result)

执行效果说明 #

运行上述代码输出为[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]，完全符合全排列的预期结果。

语法优化建议 #

• 避免使用全局变量：将结果存储和递归逻辑封装在函数内部，避免多次调用时的结果污染
• 不要在遍历过程中修改原序列：通过切片生成新的序列传入下一层递归，逻辑更清晰也不会出现遍历异常
• 避免使用内置关键字作为变量名：不要用set、list、str这类内置类型名当变量/参数名
• 递归终止条件前置：进入递归函数优先判断是否满足终止条件，符合常规回溯算法的书写规范

内容的提问来源于stack exchange，提问作者Gurjot Singh Sidhu