剑指 Offer II 084:含有重复元素集合的全排列——排序去重回溯的完整实现剖析
剑指 Offer II 084:含有重复元素集合的全排列——排序去重回溯的完整实现剖析
本文围绕《剑指 Offer(专项突击版)》第 084 题「含有重复元素集合的全排列」展开,讲解在输入数组包含重复数字时,如何通过「先排序 + 回溯 + used 标记」在搜索过程中直接剪枝去重,得到全部不重复排列。结合本仓库 题解文档 及 Solution 目录 中的 Python、Java、C++、Go、C#、Swift 六种实现,读者将掌握含重复元素排列类问题的标准去重套路,以及一种基于计数统计的备选回溯写法。
题目概览
给定一个可包含重复数字的整数集合 nums,按任意顺序返回它所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
注意输出中不能出现重复的排列:[1,1,2] 虽然可以由两个不同的 1 下标组合产生,但只能输出一次。
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
当数组无重复元素时,就是标准的 n! 个全排列。
提示:
1 <= nums.length <= 8-10 <= nums[i] <= 10
该题与主站「47. 全排列 II」为同一道题,本仓库在主站 0047.Permutations II 题解 中给出了更详细的方法叙述;与之配套的「无重复元素全排列」是 剑指 Offer II 083(对应主站 46 题)。
核心难点:used 标记去重为什么不够
「全排列」的经典回溯做法是:用一个 used 布尔数组标记每个下标是否已被选取,然后按位置从左到右填入数字,递归到第 n 层时记录一条排列,回溯时撤销标记。
原题文档的思考部分明确指出:数组含重复值时,只按 used 标记会把相同值的不同下标当成不同排列。例如 nums = [1,1,2],两个值为 1 的下标被看作两个不同的元素,于是 [1,1,2] 会被生成两次,搜索结果出现大量重复。
如果先不做处理,事后用集合 Set 对结果去重,搜索树中重复值会被整棵复制,既慢又费空间。因此更优的思路是在搜索过程中直接剪枝。
方法一:排序 + 回溯剪枝去重
去重思路
仓库题解给出的思路分两步:
- 先排序,使相等的元素在数组中相邻排列;
- 同一层去重:在 for 循环枚举第
u个位置时,若满足:
used[i] == true
或
(i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
则跳过该下标。
第二条正是剪枝核心:同一层中,如果 nums[i] 与前一个元素 nums[i - 1] 值相等,且前一个相同值还没有被使用,则跳过当前下标。这样做的效果是:对于一组相等的值,在同一层只让第一个值展开一次,强制相等元素按原始相对次序被选取,从而保证不会产生重复排列。
为什么判据是 !used[i - 1] 而不是 used[i - 1]
这里容易混淆。若条件写成 used<a href="https://link.gitcode.com/i/57e27edcbb161d24cdee277571ef2320" target="_blank">i - 1](前一个已被使用才跳过),则在回溯撤销的过程中,同一层会先让后面的相同值展开,产生重复;而写成 !used[i - 1],只有当「前一个相同值尚未被选」时才剪枝,保证相同值永远按下标从小到大被选取,这正是主站 47 题文档中「每个位置上每种值只展开一次」的含义。该条件在 Python、Java、C++、Go、Swift 五个实现中完全一致,可直接对照 [Solution.py 与 Solution.java 验证。
Python 实现
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
path = [0] * n
used = [False] * n
nums.sort()
def dfs(u):
if u == n:
res.append(path.copy())
return
for i in range(n):
if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
continue
path[u] = nums[i]
used[i] = True
dfs(u + 1)
used[i] = False
dfs(0)
return res
代码要点:
nums.sort()是去重的前置条件,必须先执行;path按固定长度n预分配,递归到u == n时用path.copy()记录快照,避免后续修改污染已保存结果;used[i] = True与dfs(u + 1)之后必须used[i] = False撤销,保证每个下标可在不同排列中复用。
Java 实现
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int n = nums.length;
boolean[] used = new boolean[n];
Arrays.sort(nums);
dfs(0, n, nums, used, path, res);
return res;
}
private void dfs(
int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (u == n) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < n; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
Java 版本使用动态的 List<Integer> path,入结果时需 new ArrayList<>(path) 拷贝一份;回溯时除了撤销 used[i],还要 path.remove(path.size() - 1) 把刚填入的元素弹出。其余剪枝逻辑与 Python 版完全一致。
C++ 实现
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> res;
vector<int> path(n, 0);
vector<bool> used(n, false);
sort(nums.begin(), nums.end());
dfs(0, n, nums, used, path, res);
return res;
}
void dfs(int u, int n, vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
if (u == n) {
res.emplace_back(path);
return;
}
for (int i = 0; i < n; ++i) {
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
path[u] = nums[i];
used[i] = true;
dfs(u + 1, n, nums, used, path, res);
used[i] = false;
}
}
};
C++ 版与 Python 版一样采用固定长度 vector<int> path(n, 0),用下标直接写入;记录结果时 res.emplace_back(path) 会拷贝当前路径,因此无需手动恢复 path。
Go 实现
func permuteUnique(nums []int) [][]int {
n := len(nums)
res := make([][]int, 0)
path := make([]int, n)
used := make([]bool, n)
sort.Ints(nums)
dfs(0, n, nums, used, path, &res)
return res
}
func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
if u == n {
t := make([]int, n)
copy(t, path)
*res = append(*res, t)
return
}
for i := 0; i < n; i++ {
if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue
}
path[u] = nums[i]
used[i] = true
dfs(u+1, n, nums, used, path, res)
used[i] = false
}
}
Go 版需要注意的是:path 切片在后续递归中会被复用,保存结果时必须 t := make([]int, n); copy(t, path) 深拷贝,否则最终所有结果会指向同一份被覆盖的底层数组。res 以指针 *[][]int 传入,在递归中通过 *res = append(*res, t) 追加。
Swift 实现
class Solution {
func permuteUnique(_ nums: [Int]) -> [[Int]] {
var res = [[Int]]()
var path = [Int]()
var used = Bool
let sortedNums = nums.sorted()
dfs(0, sortedNums.count, sortedNums, &used, &path, &res)
return res
}
private func dfs(
_ u: Int, _ n: Int, _ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ res: inout [[Int]]
) {
if u == n {
res.append(path)
return
}
for i in 0..<n {
if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue
}
path.append(nums[i])
used[i] = true
dfs(u + 1, n, nums, &used, &path, &res)
used[i] = false
path.removeLast()
}
}
}
Swift 版用 nums.sorted() 生成新数组(不改动入参),可变状态 used、path、res 通过 inout 参数传递,回溯时同样撤销标记并 path.removeLast()。
方法二:基于计数统计的回溯(C# 实现)
仓库的 Solution.cs 提供了另一种思路:不关心下标,直接对「每种数值还剩多少个」进行递归。用字典统计每个数字的出现次数,每次递归选择一个还有剩余次数的数值填入,天然保证相同值不会重复展开。
public class Solution {
public IList<IList<int>> PermuteUnique(int[] nums) {
var results = new List<IList<int>>();
var temp = new List<int>();
var count = nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
Search(count, temp, results);
return results;
}
private void Search(Dictionary<int, int> count, IList<int> temp, IList<IList<int>> results) {
if (!count.Any() && temp.Any()) {
results.Add(new List<int>(temp));
return;
}
var keys = count.Keys.ToList();
foreach (var key in keys) {
temp.Add(key);
--count[key];
if (count[key] == 0) count.Remove(key);
Search(count, temp, results);
temp.RemoveAt(temp.Count - 1);
if (count.ContainsKey(key)) {
++count[key];
}
else {
count[key] = 1;
}
}
}
}
理解要点:
nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count())将数组折叠为「值 → 剩余可用次数」的映射;- 递归终止条件为字典为空(所有数字都用完)且当前路径非空;
- 每次选择某个
key后将其计数减一,减到 0 时从字典移除;回溯时恢复计数(若已被移除则重建为 1); - 因为同一数值的所有可选取次数在单一路径上被依次消耗,相同排列不会被重复构造,因此无需排序,也无需下标去重。
该方法的时间开销与值域种类数相关,适合作为理解「按值展开」去重思路的补充实现,与主流的「按下标展开 + 排序剪枝」形成对照。
复杂度分析
从主站 47. 全排列 II 题解 的叙述可以确认本方法的复杂度结论:
- 时间复杂度 O(n × n!):需要枚举
n!个排列(去重后规模更小),每个位置枚举时还需 O(n) 时间遍历判断used与相等相邻条件; - 空间复杂度 O(n):递归栈深度为
n,外加一个长度为n的used标记数组和path路径数组。
题目约束 n <= 8,n! 最大为 40320,在回溯剪枝后实际展开的节点数远小于理论值,完全在可接受范围内。
与无重复全排列的对比
将本题与 剑指 Offer II 083「没有重复元素集合的全排列」(对应主站 46 题)对比:
| 维度 | 083 无重复全排列 | 084 含重复全排列 |
|---|---|---|
| 输入约束 | nums 中所有整数互不相同 |
可包含重复数字 |
| 去重处理 | 无需,used 直接按下标标记即可 |
需先排序,并追加 nums[i] == nums[i-1] && !used[i-1] 剪枝条件 |
| 结果数量 | n! |
去重后的不重复排列数 |
| 与主站对应 | 46. Permutations | 47. Permutations II |
两份文档的 dfs 框架完全同构,差异仅在排序与剪枝条件一行:083 只判断 !used[i],084 多出「相同值且前一个未使用则跳过」的条件。因此本题可以看作在标准全排列回溯上叠加排序 + 同层剪枝两处修改即可完成去重的典型范例。
小结
剑指 Offer II 084 的核心训练点是「含重复元素的排列类回溯去重」:先排序让相等元素相邻,再用 !used<a href="https://link.gitcode.com/i/b08498011da0e7aa986d0e95fe14796e" target="_blank">i - 1] 条件保证相同值在同一层只展开一次,从根源上消除重复排列,避免事后用集合去重的额外开销。仓库题解提供了六种语言的完整可运行实现(见 [README.md 及对应 Solution 文件),其中 C# 的计数法另辟蹊径,展示了「按值展开」的去重思路。理解这一剪枝原理后,可以自然迁移到组合、子集等其他含重复元素的枚举类问题。