调试LeetCode 46排列问题回溯算法：含索引参数版本出现重复解

你遇到的核心问题是在遍历集合remain的同时修改了集合本身，这会破坏Python集合迭代器的正常遍历逻辑，导致同一个元素被多次处理，最终生成重复排列。

错误原因详解 #

当你执行for i in remain:时，Python会创建一个绑定到当前remain集合状态的迭代器。在循环体内调用remain.remove(i)会直接修改集合的结构，虽然递归返回后用remain.add(i)恢复了集合，但迭代器的遍历顺序已经被打乱——迭代器会基于集合的实时状态继续遍历，这就可能导致某些元素被重复选中，进而生成重复的排列结果。

修复方案：遍历集合的副本 #

解决方法很简单：遍历remain的快照副本，而不是原集合。这样后续对原集合的修改不会影响当前循环的元素序列。修改后的代码如下：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state, remain):
            if len(state) == len(nums):
                solutions.append(state.copy())
                return

            # 遍历remain的列表副本，避免迭代过程中修改原集合
            for i in list(remain):
                state.append(nums[i])
                remain.remove(i)
                backtrack(state, remain)
                state.pop()
                remain.add(i)

        full_ind = set(range(len(nums)))
        state = []
        backtrack(state, full_ind)
        return solutions

更简洁的替代写法 #

如果不想手动处理集合的增删回溯，可以通过传递新集合的方式简化代码——每次递归时生成一个移除当前索引的新集合，无需在回溯时恢复原集合：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        solutions = []
        def backtrack(state, remain):
            if len(state) == len(nums):
                solutions.append(state)
                return

            for i in remain:
                # 传递新的状态和集合，无需手动回溯修改
                backtrack(state + [nums[i]], remain - {i})

        full_ind = set(range(len(nums)))
        backtrack([], full_ind)
        return solutions

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