permuteUnique代码去重逻辑失效，特殊场景返回错误结果求解答

你这段全排列去重代码的核心问题，出在去重条件的逻辑不匹配排列问题的特性，导致要么漏掉合法排列，要么生成重复排列。

先看你疑惑的这段代码：

if i > index and nums[i] == nums[i-1]:  # checking for duplicate values
    continue

为什么这个条件在组合中有效，排列中不行？ #

组合问题的本质是按顺序选取元素，不改变原数组位置，排序后只要跳过和前一个相同的元素，就能避免生成重复组合——因为选第i个元素和选第i-1个相同元素，得到的组合是完全一样的。

但排列问题的核心是交换元素位置生成不同序列，哪怕元素值相同，交换到不同位置可能得到合法的新排列，这时候单纯用「相邻元素相同就跳过」的逻辑就会出错：
比如输入[1,1,2,2]，当递归到index=1时，数组是排序后的[1,1,2,2]：

• 你的条件会跳过i=3（因为nums[3]==nums[2]），但交换index=1和i=3的元素，会得到合法排列[1,2,2,1]，这部分就被错误地漏掉了。
• 反过来，如果数组在递归交换后打乱了排序（比如变成[1,2,1,2]），此时相同元素不相邻，你的条件又检测不到重复，会生成重复排列。

正确的去重思路（交换写法） #

排列去重的关键是：在当前递归层中，记录已经用来交换到index位置的元素值，避免重复使用相同值的元素。可以用一个集合来实现这个逻辑，修改后的代码如下：

from typing import List

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []

        def backtrack(index, nums):
            if index == len(nums):
                ans.append(nums.copy())
                return 
            seen = set()  # 记录当前递归层已使用的元素值
            for i in range(index, len(nums)):
                if nums[i] in seen:
                    continue
                seen.add(nums[i])
                nums[index], nums[i] = nums[i], nums[index]
                backtrack(index + 1, nums)
                nums[index], nums[i] = nums[i], nums[index]

        backtrack(0, nums)
        return ans

逻辑说明 #

• 每次进入递归层时，用seen集合记录已经交换到index位置的元素值。
• 遍历到i时，如果nums[i]已经在seen里，说明这个值的元素已经被用来生成过当前位置的排列，直接跳过。
• 否则将其加入集合，交换后递归，回溯时再交换回来，保证后续循环的数组状态正确。

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