LeetCode 46. Permutations回溯解法错误：输出含重复元素排查

你的代码存在几个关键问题，直接导致输出重复且缺失大量正确排列：

• 起始路径单一：仅调用dfs('', nums[0])，只从第一个元素开始构建排列，完全漏掉了以2、3开头的所有可能。
• 递归参数传递错误：递归调用dfs(curr + str(l), t)时，错误拼接了上一层的参数l而非当前遍历的t，导致curr字符串被重复写入元素，最终生成带重复数字的排列。
• 冗余的visit列表：每次DFS函数内都重新定义visit = []，append和pop操作完全没起到标记已访问元素的作用，属于无效代码。
• 字符串判断的缺陷：用str(t) not in curr判断元素是否已使用，虽然当前测试用例是个位数整数没问题，但如果nums包含多位数（比如12）会出现误判，且这种方式效率极低。

修正后的代码 #

用数组保存当前路径，通过访问标记数组来追踪已使用元素，同时覆盖所有起始情况：

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        perms = []
        n = len(nums)
        
        def dfs(curr_path, visited):
            # 路径长度等于数组长度时，保存当前排列
            if len(curr_path) == n:
                perms.append(curr_path.copy())
                return
            # 遍历所有元素
            for i in range(n):
                if not visited[i]:
                    # 标记元素已访问，加入当前路径
                    visited[i] = True
                    curr_path.append(nums[i])
                    # 递归深入
                    dfs(curr_path, visited)
                    # 回溯：撤销标记，移出当前路径
                    curr_path.pop()
                    visited[i] = False
        
        # 从空路径开始，初始化访问标记数组
        dfs([], [False] * n)
        return perms

测试结果 #

针对nums = [1,2,3]，修正后的代码会输出预期的全排列：

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

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