Python全排列实现：数组版与字符串版函数输出不一致排查

两个函数逻辑看似对齐，实际问题出在Python可变/不可变对象的行为差异，以及回溯操作的作用域不匹配：

• 字符串版本运行正常的原因
  字符串是不可变类型，permutation_str中执行res = res + str[i]时，不会修改原有字符串对象，而是生成一个全新的字符串，绑定到当前函数栈帧的局部变量res上。传入下层递归的是这个新生成的独立字符串，下层递归对自身局部变量res的修改、重绑定，完全不会影响当前层的res值。最后回溯执行res = res[:-1]也是当前层局部变量的重绑定操作，回溯逻辑完全成立。
• 数组版本输出异常的原因
  列表是可变类型，permutation_arr中执行res.append(arr[i])是原地修改传入的列表对象，全程所有递归层持有的res都指向同一个列表实例。但回溯时写的res = res[:-1]操作，是生成了一个去掉末尾元素的新列表，仅把这个新列表绑定到当前函数栈帧的局部变量res上，并没有修改之前被append操作改动的原列表对象。
  简单说就是：你往原列表里塞了元素，回溯的时候没把原列表里的元素删掉，只是让当前层的局部变量指向了一个新列表，上层递归持有的还是那个被塞了多余元素、状态错乱的原列表，自然输出不符合预期。

修复方案 #

把数组版本回溯行的res = res[:-1]替换成原地删除操作res.pop()，和前面的append原地操作对应即可，修复后的数组版函数：

def permutation_arr(res, arr):
    if len(arr) == 0:
        print(res)
    
    for i in range(len(arr)):
        res.append(arr[i])
        permutation_arr(res, arr[:i] + arr[i+1:])
        res.pop() # 原地删除最后一个元素，真正回滚原列表状态

permutation_arr([], [1,2,3])

运行后即可和字符串版本输出一致的全排列结果。

补充：如果你非要用切片写法做回溯，那递归传参的时候就不能传原res，要传切片生成的新列表，比如把permutation_arr(res, arr[:i] + arr[i+1:])改成permutation_arr(res + [arr[i]], arr[:i] + arr[i+1:])，同时去掉前面的append和后面的回溯赋值，不过这种写法会生成大量多余列表对象，性能远不如append+pop的原地回溯写法。

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