为何计算列表全排列的回溯算法无法返回所有排列且结果重复？

你实现的全排列代码存在两个关键问题，导致输入[1,2,3]时输出全是[1,2,3]：

1. 仅添加列表引用而非副本 #

当执行res.append(nums)时，你向结果列表中添加的是nums列表的内存引用，而非当前状态下的列表副本。后续的回溯交换操作会直接修改这个列表的内容，最终res里的所有元素都会指向同一个列表——回溯完成后恢复初始状态的[1,2,3]。

解决方法：添加列表的副本到结果中，替换为：

res.append(nums.copy())  # 或者 nums[:]

2. 循环范围与终止条件不匹配 #

原代码中length = len(nums) - 1，循环用range(l, length)，这会导致循环的终止索引是length-1（range是左闭右开规则）。以输入[1,2,3]为例，length=2，循环range(l, 2)意味着：

• 当l=0时，i只能取0、1，漏掉了i=2；
• 当l=1时，i只能取1，漏掉了i=2；
  这直接导致最后一个元素从未参与交换，无法生成包含最后一个元素位置变化的排列。

同时，终止条件if l == length也存在逻辑偏差：当l等于len(nums)-1时，已经是最后一个元素的位置，此时应该直接添加当前列表状态到结果，但原循环没覆盖到这个位置的交换。

修正方案：

• 去掉length变量，直接使用len(nums)；
• 循环范围改为range(l, len(nums))；
• 终止条件改为if l == len(nums)，此时所有元素都已固定位置，添加结果即可。

修正后的完整代码 #

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(nums, l):
            # base case：所有元素已固定位置
            if l == len(nums):
                res.append(nums.copy())
                return
            for i in range(l, len(nums)):
                # swap
                nums[l], nums[i] = nums[i], nums[l]
                dfs(nums, l+1)
                # backtrack
                nums[l], nums[i] = nums[i], nums[l]
        dfs(nums, 0)
        return res

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