企业官网建设流程全解析

• 示例工程

导读

本文基于 doocs/leetcode 开源题解仓库中 0047.Permutations II 题解文档 展开，系统讲解如何在包含重复数字的数组中生成所有不重复的全排列。文章覆盖问题描述、排序 + 回溯算法的完整推导、去重条件的精妙设计、时间复杂度分析，以及 Python、Java、C++、Go、TypeScript、Rust、JavaScript、C# 八种语言的仓库源码实现。读完本文，你将掌握“含重复元素组合/排列类问题”最核心的去重套路，并能直接对照仓库源码在本地运行验证。

一、题目解析：从“全排列”到“不重复全排列”

LeetCode 47 号题（英文题解 / 中文题解）的描述如下：

给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。

它与 46 号题的关键差异在于：46 号题保证数组元素互不相同，只需输出全部 $n!$ 个排列；而 47 号题数组中可能存在重复值，若直接套用无去重的回溯，会生成大量重复排列，必须去重。

示例与约束

示例 1：输入nums = [1,1,2]，输出：

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

共有 3 个结果，而不是朴素的 $3! = 6$ 个——因为两个1交换位置产生的排列（如[1,1,2]）被认为是同一个。

示例 2：输入nums = [1,2,3]（无重复），输出全部 6 个排列：

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

约束条件：

注意n ≤ 8意味着 $n!$ 最大为 40320，回溯枚举在规模上是完全可行的，但重复分支会让实际搜索树远大于理论排列数，这正是去重优化的价值所在。

二、核心思路：为什么不能“先枚举再去重”

最朴素的想法是：照搬 46 号题的回溯生成所有排列，最后用集合（Set）过滤掉重复结果。题目官方题解文档中的“思考”部分明确指出这条路的问题：

直接套用上一题的回溯，再用集合去除重复结果，当 $n \le 8$ 且数组含相同数字时，搜索树会被复制多份，事后去重既慢又费空间。

关键在于：两个相同的数在同一层（同一位置）交换顺序，得到的仍是同一个排列。例如数组[1,1,2]，在位置 0 选择下标 0 的1与选择下标 1 的1，后续无论怎么填，产出的是完全相同的排列集合。因此——

相同值在同一层只应被选择一次。

如果先完整枚举再集合去重，重复的整棵子树都会被完整地搜索一遍、存一遍再丢掉，浪费时间和空间。

正确做法是：

1. 先对数组排序，让相等的数字相邻排列；
2. 回溯时在每一层跳过“前一个相同值尚未使用”的分支；
3. 这样每个位置上每种值只展开一次，所有生成的排列天然不重复，无需事后去重。

三、算法设计：排序 + 回溯（visited 标记法）

3.1 状态定义与递归函数

设计递归函数 $\textit{dfs}(i)$，表示当前需要填写第 $i$ 个位置的数。同时维护三个数据结构：

3.2 递归终止条件

• 若 $i = n$，说明 0 到 $n-1$ 共n个位置全部填写完毕，将当前t的快照加入答案数组，然后返回。

3.3 单层枚举与剪枝条件

否则，枚举第 $i$ 个位置要填的数 $nums[j]$（$j$ 的范围是 $[0, n-1]$），需要同时满足两个条件：

1. 未被使用：vis[j] == false；
2. 不产生重复：nums[j]与前一个被枚举的数不同。

合并成一个跳过条件（以 Java 为例）：

if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) { continue; }

满足条件后，执行“填数 → 标记 → 递归 → 回溯”四步：

t.add(nums[j]); vis[j] = true; dfs(i + 1); vis[j] = false; t.remove(t.size() - 1);

最后在permuteUnique主函数中先Arrays.sort(nums)，再调用dfs(0)从第 0 个位置开始填写，返回答案数组。

3.4 去重条件的深层理解

nums[j] == nums[j - 1] && !vis[j - 1]是本题的灵魂，它的含义是：

当nums[j]与排序后紧邻的前一个元素相等，且前一个相同元素当前还没有被使用时，跳过本次选择。

为什么这样能去重？因为排序后相等的元素相邻。假设两个相同的值分别位于下标a和b（a < b）。在同一层枚举时：

• 如果先选了下标b的值，此时下标a的值未被使用（!vis[a]），说明相等元素破坏了原有的相对顺序，这种分支产生的结果与“先选a”的分支完全重复，应当剪掉；
• 反过来，先选下标a（vis[a] = true）后，后续层再选下标b时因为vis[a] == true，条件!vis[j-1]为假，不会被误剪。

也就是说：这强制了相等的元素只能按照它们在排序后数组中的相对顺序依次被选取，每个位置上每种值只展开一次，从根源上杜绝了重复排列。这个技巧同样是剑指 Offer II 084（含有重复元素集合的全排列）的标准解法，那道题在仓库中与本题互为镜像，可相互印证。

四、复杂度分析

• 时间复杂度：$O(n \times n!)$。需要完成 $n!$ 次枚举，每次枚举需要 $O(n)$ 的时间判断重复并复制结果。虽然数组含重复值时实际枚举数少于 $n!$，但上界仍为 $O(n \times n!)$。
• 空间复杂度：$O(n)$。需要vis标记数组记录每个位置是否被使用；递归调用栈深度为n；临时排列t长度为n。三者都是 $O(n)$ 量级，不计算答案数组本身占用的空间。

注：当输入无重复时，枚举次数恰好为 $n!$；有重复时由于剪枝，实际遍历节点数显著减少，这正是“先排序剪枝”优于“事后集合去重”的原因。

五、多语言实现：八种语言的仓库源码

doocs/leetcode 仓库为本题提供了 8 种语言的可直接运行实现，对应文件位于 0047.Permutations II 目录：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs。以下代码与仓库文件内容一致。

5.1 Python3（Solution.py）

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def dfs(i: int): if i == n: ans.append(t[:]) return for j in range(n): if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]): continue t[i] = nums[j] vis[j] = True dfs(i + 1) vis[j] = False n = len(nums) nums.sort() ans = [] t = [0] * n vis = [False] * n dfs(0) return ans

要点：t[i] = nums[j]按位置直接写入，递归结束只需还原vis[j]，无需弹出操作；ans.append(t[:])用切片复制快照。

5.2 Java（Solution.java）

class Solution { private List<List<Integer>> ans = new ArrayList<>(); private List<Integer> t = new ArrayList<>(); private int[] nums; private boolean[] vis; public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); this.nums = nums; vis = new boolean[nums.length]; dfs(0); return ans; } private void dfs(int i) { if (i == nums.length) { ans.add(new ArrayList<>(t)); return; } for (int j = 0; j < nums.length; ++j) { if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) { continue; } t.add(nums[j]); vis[j] = true; dfs(i + 1); vis[j] = false; t.remove(t.size() - 1); } } }

要点：Java 用ArrayList作为可变路径，递归前后分别add与remove维护状态；ans.add(new ArrayList<>(t))构造拷贝，防止后续修改污染已存结果。

5.3 C++（Solution.cpp）

class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { ranges::sort(nums); int n = nums.size(); vector<vector<int>> ans; vector<int> t(n); vector<bool> vis(n); auto dfs = & { if (i == n) { ans.emplace_back(t); return; } for (int j = 0; j < n; ++j) { if (vis[j] || (j && nums[j] == nums[j - 1] && !vis[j - 1])) { continue; } t[i] = nums[j]; vis[j] = true; dfs(i + 1); vis[j] = false; } }; dfs(0); return ans; } };

要点：使用 C++23 的ranges::sort与递归 lambda（this auto&& dfs允许 lambda 内部递归调用自身）；t为定长数组按下标写入。

5.4 Go（Solution.go）

func permuteUnique(nums []int) (ans [][]int) { slices.Sort(nums) n := len(nums) t := make([]int, n) vis := make([]bool, n) var dfs func(int) dfs = func(i int) { if i == n { ans = append(ans, slices.Clone(t)) return } for j := 0; j < n; j++ { if vis[j] || (j > 0 && nums[j] == nums[j-1] && !vis[j-1]) { continue } vis[j] = true t[i] = nums[j] dfs(i + 1) vis[j] = false } } dfs(0) return }

要点：使用 Go 1.21+ 的slices.Sort与slices.Clone；利用命名返回值ans直接append。

5.5 TypeScript（Solution.ts）

function permuteUnique(nums: number[]): number[][] { nums.sort((a, b) => a - b); const n = nums.length; const ans: number[][] = []; const t: number[] = Array(n); const vis: boolean[] = Array(n).fill(false); const dfs = (i: number) => { if (i === n) { ans.push(t.slice()); return; } for (let j = 0; j < n; ++j) { if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) { continue; } t[i] = nums[j]; vis[j] = true; dfs(i + 1); vis[j] = false; } }; dfs(0); return ans; }

要点：nums.sort((a, b) => a - b)显式传入比较器（数字默认按字符串排序，必须指定）；t.slice()复制结果。

5.6 Rust（Solution.rs）

impl Solution { pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> { nums.sort(); let n = nums.len(); let mut ans = Vec::new(); let mut t = vec![0; n]; let mut vis = vec![false; n]; fn dfs( nums: &Vec<i32>, t: &mut Vec<i32>, vis: &mut Vec<bool>, ans: &mut Vec<Vec<i32>>, i: usize, ) { if i == nums.len() { ans.push(t.clone()); return; } for j in 0..nums.len() { if vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1]) { continue; } t[i] = nums[j]; vis[j] = true; dfs(nums, t, vis, ans, i + 1); vis[j] = false; } } dfs(&nums, &mut t, &mut vis, &mut ans, 0); ans } }

要点：由于 Rust 的所有权限制，递归辅助函数dfs通过&mut引用显式传入t、vis、ans，这是 Rust 版与其他语言在写法上的最大差异。

5.7 JavaScript（Solution.js）

/** * @param {number[]} nums * @return {number[][]} */ var permuteUnique = function (nums) { nums.sort((a, b) => a - b); const n = nums.length; const ans = []; const t = Array(n); const vis = Array(n).fill(false); const dfs = i => { if (i === n) { ans.push(t.slice()); return; } for (let j = 0; j < n; ++j) { if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) { continue; } t[i] = nums[j]; vis[j] = true; dfs(i + 1); vis[j] = false; } }; dfs(0); return ans; };

5.8 C#（Solution.cs）

public class Solution { private List<IList<int>> ans = new List<IList<int>>(); private List<int> t = new List<int>(); private int[] nums; private bool[] vis; public IList<IList<int>> PermuteUnique(int[] nums) { Array.Sort(nums); int n = nums.Length; vis = new bool[n]; this.nums = nums; dfs(0); return ans; } private void dfs(int i) { if (i == nums.Length) { ans.Add(new List<int>(t)); return; } for (int j = 0; j < nums.Length; ++j) { if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) { continue; } vis[j] = true; t.Add(nums[j]); dfs(i + 1); t.RemoveAt(t.Count - 1); vis[j] = false; } } }

六、与 46 号题（Permutations）的对比

本题解法是 46. 全排列 回溯解法的直接扩展。对比两者的核心代码（均为 Java 版）可以发现唯一实质差异：

46 号题（元素唯一，无需排序与去重），见 0046.Permutations/Solution.java：

for (int j = 0; j < nums.length; ++j) { if (!vis[j]) { // 只需判断未使用 vis[j] = true; t.add(nums[j]); dfs(i + 1); t.remove(t.size() - 1); vis[j] = false; } }

47 号题（含重复，先排序 + 同层去重）：

for (int j = 0; j < nums.length; ++j) { if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) { continue; // 额外剪掉同值不同下标的重复分支 } ... }

延伸阅读：仓库中剑指 Offer II 084（含有重复元素集合的全排列）与本题完全同源（其题面注明“与主站 47 题相同”），其解法还额外提供了基于计数的递归写法（C# 版用Dictionary统计每个数字的出现次数，枚举时按“值”而非“下标”展开），可作为理解去重本质的对照参考。

七、常见误区与易错点

1. 忘记排序：去重条件nums[j] == nums[j - 1]依赖相等元素相邻，不排序则条件失效。
2. 去重条件写成!vis[j - 1]时逻辑颠倒：必须跳过“前一个相同值尚未使用”的情况；若写成“已使用才跳过”，会把合法分支剪掉，导致结果缺失。
3. 回溯时忘记还原状态：vis[j] = false（以及 Java/C#/JS 中的路径弹出操作）必须执行，否则影响后续枚举。
4. 结果拷贝时机错误：必须存入t的快照（t[:]、new ArrayList<>(t)、slices.Clone(t)、t.slice()），若直接存入引用，后续回溯会污染已存结果。
5. JS/TS 排序比较器：nums.sort()默认按字典序排序，数字数组必须写(a, b) => a - b。

八、总结

LeetCode 47 号题“全排列 II”是回溯算法中“含重复元素去重”的经典模板题，其方法论可以推广到子集、组合等所有“选择集合含重复值”的问题：

1. 排序让相等元素相邻，是去重的前提；
2. 同层剪枝：nums[j] == nums[j-1] && !vis[j-1]保证相同值在同一位置只展开一次；
3. 先剪枝后递归，避免事后集合去重带来的时间和空间浪费。

仓库中 0047.Permutations II 目录 下 8 种语言的Solution.*文件可直接复制运行；对照 46 号题解 与 剑指 Offer II 084 进行横向比较，即可彻底吃透这一经典去重套路。

• 示例工程