BM56　有重复项数字的全排列¶

中等通过率 36.07%python3核心代码模式样例通过牛客 AC递归

牛客原题　源码

讲解章节：DFS 深度优先搜索

一句话

排序后回溯，同层遇到「与前一个相同且前一个未被使用」就剪枝。

解题思路¶

这题考什么¶

骨架与 BM55 完全一致（选 -> 递归 -> 撤销，配 used 标记），新增的唯一问题是重复数字会产出一模一样的排列： [1,1,2] 里两个 1 谁先谁后，写出来看不出区别，却会被算成两份。

先排序让相同的数字相邻，再在同一层里加一条剪枝：

if j > 0 and num[j] == num[j-1] and not used[j-1]:
    continue

读法是「同一组相同数字，必须按下标从左到右依次使用」。展开说：num[j] 与 num[j-1] 相同而 num[j-1] 此刻没被占用，说明在当前这一层里要么还没轮到 j-1（它在本层是另一条平行分支），要么它已经用完撤销了；两种情况下选 j 都会重复出一份「先用后者」的排列，直接跳过。

条件必须是「前一个未被使用」：

used[j-1] 为真   前一个正在被使用，这是同一组内「1 之后再接 1」的合法递进，放行
used[j-1] 为假   同层的平行分支，选 j 与刚才选 j-1 产出完全相同的结果，剪掉

去重回溯的这条剪枝见记忆化搜索与剪枝。

数据规模与复杂度¶

0 < n <= 8，元素取值 -1 到 5，时限其他语言 2 秒。互不相同的排列最多 8 的阶乘 = 40320 份，重复元素只会让它更少；时间 O(n 乘 n 的阶乘)，递归深度 8，空间 O(n)（答案不计）。

坑在哪¶

排序不能省，它同时担着两件事：让相同数字相邻，剪枝才抓得到；让产出直接是字典序升序，而题面正是这么要求的，牛客严格比对顺序。
剪枝条件写反成 used[j-1] 也能去重，但代价是先走一段注定失败的分支：那种写法要求同组数字从右往左用，于是「先选下标 0 的 1」这条路永远拼不完整，白搜一层才回头。写成「未被使用」则在同层第一次就剪掉。
三个条件缺一不可。少了 j > 0 会越界访问 num[-1]（Python 不报错，而是悄悄取到末位元素，剪出错误结果）；少了值相等的判断会把不同的数字也剪掉。
收答案照样要 path[:] 拷贝，理由同 BM55：path 是全程复用的同一个列表。
剪枝只在同一层生效，跨层由 used 负责，两者职责不同，不能互相替代。

样例复核¶

[1,1,2] 排序后仍是 [1,1,2]。

第一层 j=0 选 1  ->  继续往下
第一层 j=1 也是 1，但 used[0] 为假，剪掉（否则整枝重复）
第一层 j=2 选 2  ->  继续往下

产出 [[1,1,2],[1,2,1],[2,1,1]]，与样例的顺序逐字一致。

参考实现¶

solutions/nowcoder/BM56/sol.py
from typing import List, Optional


class Solution:
    def permuteUnique(self, num: List[int]) -> List[List[int]]:
        num = sorted(num)               # 排序：相同数字相邻，且输出即字典序
        n = len(num)
        # res 收答案，path 是当前正在拼的排列，used 记录哪些下标已被占用
        res = []
        path = []
        used = [False] * n

        def dfs():
            # 填满即成一份答案，path[:] 的拷贝不能省
            if len(path) == n:
                res.append(path[:])
                return
            for j in range(n):
                if used[j]:
                    continue            # 这个下标已经在 path 里了
                # 同一组相同数字必须从左往右依次用，否则同层重复
                if j > 0 and num[j] == num[j - 1] and not used[j - 1]:
                    continue            # 同层重复分支，剪掉
                # 选 -> 递归 -> 撤销，三步成对；撤销漏掉一处，后面的分支就会读到脏状态
                used[j] = True
                path.append(num[j])
                dfs()
                path.pop()
                used[j] = False

        dfs()
        return res

BM56 有重复项数字的全排列¶