Python排列代码未返回正确排列结果问题排查

嘿，你已经离正确结果很近啦！问题确实和Python中可变对象的引用特性有关——你在保存排列结果的时候，存的是列表的引用，而非当前状态的副本。

问题根源 #

Python里的列表属于可变对象。当你执行self.permutations.append(chosen)时，并没有把当前chosen里的元素复制一份存进去，而是把chosen这个列表本身的"引用"添加到了结果列表中。后续递归过程里，你不断通过chosen.remove(num)修改这个列表的内容，等到整个递归结束时，所有引用指向的都是被清空后的chosen，所以最终返回的结果全是空列表。

修复方案 #

只需要在保存结果时，创建chosen的副本即可。有几种简单的实现方式：

• 用list(chosen)生成副本
• 用切片语法chosen[:]生成副本
• 用列表的copy()方法（Python 3.3+支持，你的代码是Python 2，前两种更适配）

修改后的核心代码片段：

if nums == []:
    print chosen
    # 这里改为添加当前chosen的副本
    self.permutations.append(list(chosen))

完整修复后的代码 #

class Solution:
    def __init__(self):
        self.permutations = []
    def permute_helper(self, nums, chosen):
        if nums == []:
            print chosen
            self.permutations.append(list(chosen))
        else:
            for num in nums:
                #choose
                chosen.append(num)
                temp = nums[:]
                temp.remove(num)
                #explore
                self.permute_helper(temp, chosen)
                #un-choose
                chosen.remove(num)
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.permute_helper(nums, [])
        return self.permutations
s = Solution()
input = [1,2,3]
print s.permute(input)

运行结果 #

执行后就能得到你期望的输出：

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

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