labuladong讲解

你好，同学。我们已经掌握了基础的全排列生成。今天我们要面对的是全排列问题的“升级版”——全排列 II (Permutations II)。

在 NOI 竞赛中，处理“包含重复元素”的排列组合问题是极高频的考点。这要求你不仅会写基础搜索，还要深刻理解搜索树的去重机制。

一、 题目描述 (NOI 风格)

题目名称：全排列 II (Permutations II) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个可包含重复数字的序列 $A$，按任意顺序输出所有不重复的全排列。

【输入格式】 输入共两行。 第一行包含一个整数 $n$，表示序列中元素的个数。 第二行包含 $n$ 个以空格隔开的整数，表示序列 $A$ 中的元素。

【输出格式】 输出若干行，每行表示一个不重复的全排列，元素之间用空格隔开。

【样例输入】

3
1 1 2

【样例输出】

1 1 2
1 2 1
2 1 1

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 8$，序列中元素取值在 $[-10, 10]$ 之间。 （注：虽然 $n$ 规模较小，但本题重点在于去重逻辑。掌握此方法后，可应对更复杂的约束搜索题。）

二、 预备知识点

1. 回溯算法 (Backtracking)：通过递归枚举所有可能。
2. 排序 (Sorting)：处理重复元素的先决条件。只有排序后，相同的元素才会相邻，便于判断。
3. 标记数组 (used array)：记录当前路径已使用的元素索引。
4. 树层去重 (Tree-level Pruning)：核心技巧，用于在搜索树的同一层过滤掉相同的数值。

三、 启发式思路引导：草稿纸上的推理

假设我们要对 {1, 1, 2} 进行全排列。如果按普通全排列搜，会得到两个 {1, 1, 2}。

1. 为什么会产生重复？

在草稿纸上画出搜索树的第一层：

• 选择第一个 1（索引 0）作为开头 $\rightarrow$ 产生一系列排列。
• 选择第二个 1（索引 1）作为开头 $\rightarrow$ 产生一模一样的一系列排列。

2. 关键：如何剪掉多余的分支？

为了保证“同一位置不重复选相同数值”，我们需要：

1. 对原数组进行升序排序。
2. 在搜索循环中，如果发现当前元素 nums(i) 与前一个元素 nums(i-1) 相同：
   • 我们需要看 nums(i-1) 是否正在被使用。
   • 如果 nums(i-1) 在当前层刚刚被撤销使用（即 used(i-1) == false），说明我们正准备用一个同样的数开启一个重复的分支。
   • 结论：此时直接 continue 跳过。

四、 复杂度分析与建议

• 时间复杂度：
  • 最坏情况下（元素各不相同）为 $O(n \cdot n!)$。
  • 当重复元素较多时，实际搜索分支远少于 $n!$。
• 空间复杂度：
  • 递归深度 $O(n)$。
  • 标记数组 $O(n)$。
• 优化建议： 在 NOI 赛场上，如果你对 used(i-1) == false 还是 true 感到困惑，请记住：false 代表“树层去重”（效率更高），true 代表“树枝去重”（逻辑亦可通行但搜索量大）。

五、 算法流程图 (C++14 风格伪代码)

请严格按照此逻辑在草稿纸上模拟。注意：Mermaid 语法中括号已特殊处理。

graph TD
    Start(开始) --> SortAction("对序列 nums 排序")
    SortAction --> Init("初始化 path 数组和 used 标记数组")
    Init --> CallDFS("调用 DFS(深度 0)")

    subgraph DFS_Process [递归函数 DFS-depth]
    CheckDepth{depth == n ?}
    CheckDepth -- Yes --> Output("输出当前 path 并返回")
    CheckDepth -- No --> LoopInit("循环 i 从 0 到 n-1")
    
    LoopInit --> CheckUsed{"used(i) 为真 ?"}
    CheckUsed -- Yes --> NextI("i++ 继续循环")
    CheckUsed -- No --> CheckDup{"i 大于 0 且 nums(i) == nums(i-1) 且 used(i-1) 为假 ?"}
    
    CheckDup -- Yes --> NextI
    CheckDup -- No --> Action("标记 used(i) 为真")
    
    Action --> Push("path.push_back(nums(i))")
    Push --> Recur("递归 DFS(depth + 1)")
    Recur --> Pop("回溯 path.pop_back")
    Pop --> Unmark("恢复 used(i) 为假")
    Unmark --> NextI
    end

    Output --> End(结束)

六_ 读题关键词总结

在 NOI 竞赛中，遇到排列组合类题目，请扫描这些关键词：

1. “不重复的全排列” (Unique Permutations)：暗示必须有去重机制，不能简单的 $n!$ 枚举。
2. “包含重复数字” (Duplicates)：这是最强的信号，要求你立刻想到 sort + 相邻判断。
3. “任意顺序”：意味着后台通常有 SPJ，或者对输出顺序没有特定的字典序要求，但为了方便实现，通常我们还是按字典序搜。

教练寄语： “全排列 II”是全排列问题的终点，也是复杂约束搜索的起点。理解了 used(i-1) == false 这一行剪枝逻辑，你就真正理解了搜索树的水平截断。这比死记硬背代码要重要得多！多在草稿纸上模拟几次 {1, 1, 2} 的搜索过程，你会豁然开朗。加油！