LeetCode 47. 全排列 II:排序 + 回溯剪枝去重的多语言解法详解
LeetCode 47. 全排列 II:排序 + 回溯剪枝去重的多语言解法详解
本文以 doocs/leetcode 仓库中 0047.Permutations II 题解 为主体,系统讲解"可含重复数字的序列如何生成不重复全排列"这一经典回溯问题:先排序让重复数字相邻,再通过一条剪枝条件让"同一层中每种值只被选择一次",从而在搜索源头去掉重复分支。读完本文,你将掌握该题的标准解法框架、去重条件的底层语义、完整的复杂度分析,以及 Python3 / Java / C++ / Go / TypeScript / Rust / JavaScript / C# 八种语言的仓库级实现。
一、题目与约束
题目要求:给定一个可能包含重复数字的序列 nums,按任意顺序返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
数据约束:
1 <= nums.length <= 8-10 <= nums[i] <= 10
从仓库中该题目录的元信息(README.md 的 front matter)可以看到,本题的标签为:数组、回溯、排序。这正是解题路径的浓缩——"数组"是输入形态,"排序"是去重的前置手段,"回溯"是穷举所有排列的算法骨架。
与上一题 46. 全排列 相比,本题唯一但关键的差异在于:nums 中允许出现重复数字,因此朴素回溯会产出大量重复排列,必须引入去重机制。46 题中 nums 的所有整数互不相同,直接 DFS 即可;47 题在此基础上增加了一条剪枝条件。
二、思路演进:为什么不能直接"回溯 + 集合去重"
最直觉的做法是把 46 题的回溯原封不动搬过来,最后用集合(set)把重复排列过滤掉。从算法正确性上讲这没有问题,但存在明显的效率缺陷:
- 当
n <= 8且数组中存在相同数字时,整个子树会被复制多份。例如[1,1,2]中两个1在回溯树中会各自展开一遍,产生重复的搜索分支; - 事后去重既慢又费空间:重复结果先生成、再被丢弃,白白消耗时间与内存。
原文档的"思考"部分点明了问题的本质:
两个相同的数在同一层交换顺序,得到的仍是同一个排列。因此相同值在同一层只应被选择一次。
基于这一观察,正确的做法是:先排序让相等的数相邻,再在同一层跳过"前一个相同值尚未使用"的情况。这样每个位置上每种值只展开一次,生成的所有排列天然不重复,无需事后过滤。
三、排序 + 回溯:核心算法
算法分为两步:
- 预处理:对
nums升序排序。排序后,所有相等的数字都聚拢在相邻位置,为去重剪枝创造条件。 - 回溯:设计递归函数
dfs(i),表示当前需要填写第i个位置的数。具体逻辑:- 若
i == n(n为数组长度),说明所有位置已填完,将当前排列加入答案数组并返回; - 否则枚举
j ∈ [0, n-1],将nums[j]填入第i个位置。要求nums[j]未被使用,并且与前面枚举到的数不重复,这样才能保证当前排列不重复;满足条件后递归调用dfs(i + 1)填写下一个位置,递归返回后撤销标记(回溯)。
- 若
3.1 去重剪枝条件的语义
整个算法的灵魂在于循环开头的那条剪枝语句,例如 Python 版本:
if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
continue
它由三个子条件组成,依次判断:
| 子条件 | 含义 |
|---|---|
vis[j] |
nums[j] 已经在当前排列的前面位置被使用,不能再选 |
nums[j] == nums[j - 1] |
当前候选与前一个候选值相等(因已排序,相等的值必然相邻) |
not vis[j - 1] |
前一个相同值尚未被使用 |
当三者同时成立时跳过 nums[j]。可以这样理解:在排好序的数组中,一组相等值(如两个 1)中,只有"最靠左的那个可用副本"才有资格被放到当前层。一旦前一个相等值还没被用过,后面的相等副本一律跳过,于是"同一种值在同一层只会被选择一次",重复分支在源头就被剪掉了。
需要说明的是,这种"剪左留右"与镜像写法"vis[j - 1](剪右留左)"在逻辑上是等价的,都能保证去重;本仓库统一采用 !vis[j - 1] 这种"前一个相同值尚未使用则跳过"的形式,它保证相等元素在排列中始终按原始顺序被选中,语义更直观。
3.2 手推一遍 [1,1,2]
以 nums = [1,1,2](排序后下标 0、1、2 分别为 1,1,2)为例,走一遍递归主路径:
dfs(0):j=0选1填入第 0 位,递归dfs(1);dfs(1):j=0已被使用跳过;j=1因nums[1] == nums[0]且!vis[0]不成立(vis[0]为 true)而允许选择,填入第 1 位得到[1,1,_];dfs(2)中j=2选2,得排列[1,1,2];- 回溯后
dfs(1)继续j=2选2,dfs(2)中选1,得排列[1,2,1]; - 回到
dfs(0):j=1时nums[1] == nums[0]且!vis[0]为 true,被剪枝跳过——这正是两个1的重复分支被消除的关键; j=2选2填入第 0 位,后续依次选两个1,得排列[2,1,1]。
最终只输出 [[1,1,2],[1,2,1],[2,1,1]] 三个不重复排列,与题目示例完全一致。
四、多语言实现
仓库在 solution/0000-0099/0047.Permutations II/ 目录下为每种语言提供了独立源码文件(Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs),以下代码与 README.md 及对应 Solution.* 文件完全一致。
4.1 Python3
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 = [0] * n 预分配定长列表,按位置写入;t[:] 在记录答案时拷贝快照,避免后续回溯改写污染已保存的结果。
4.2 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 版本用成员变量承载 ans、t、nums、vis,路径用 t.add / t.remove(t.size() - 1) 动态维护;j > 0 与 Python 的 j 等价,用于避免数组越界。
4.3 C++
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++20 的 ranges::sort,并使用了带显式自身参数(this auto&& dfs)的递归 lambda,从而可以在函数体内直接递归调用自身。
4.4 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
}
要点:使用 slices.Sort(Go 1.21+)与 slices.Clone 拷贝快照;返回值通过命名返回值 (ans [][]int) 直接返回。
4.5 TypeScript
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 可能包含负数,排序时显式传入比较函数 (a, b) => a - b,保证按数值升序而非字典序排列;t.slice() 生成快照副本。
4.6 Rust
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 的递归函数不能直接闭包捕获多个可变借用,因此将 nums、t、vis、ans 全部作为参数显式传入,通过 &mut 共享可变状态;t.clone() 产生排列快照。
4.7 JavaScript
/**
* @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;
};
要点:与 TypeScript 实现同构,t.slice() 在记录答案时复制当前排列,避免引用共享导致结果互相覆盖。
4.8 C#
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;
}
}
}
要点:与 Java 版结构一致,通过 new List<int>(t) 拷贝快照、t.RemoveAt(t.Count - 1) 在回溯时撤销上一步选择。
五、复杂度分析
设数组长度为 n:
- 时间复杂度:O(n × n!)。需要进行
n!次枚举(去重后排列总数不超过n!),每次枚举需要 O(n) 的时间来判断是否重复(主要开销在vis数组的扫描与相等性判断); - 空间复杂度:O(n)。递归深度为
n,需要一个长度n的标记数组vis记录每个位置是否被使用,以及长度n的排列构造数组t;输出答案所占的空间不计入辅助空间。
结合题目约束 n <= 8,n! 最大为 8! = 40320,规模完全在可枚举范围内,该做法在实际运行中非常高效;同时 nums[i] 取值范围为 [-10, 10],排序与相等性判断均不涉及溢出等边界问题。
六、仓库源码与相似题目
- 本题完整文档与全部实现:README.md(中文)、README_EN.md(英文);
- 各语言独立源码文件:
Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs,均位于 solution/0000-0099/0047.Permutations II/ 目录下,可直接对照阅读或本地运行验证; - 相似题目:46. 全排列——无重复元素的回溯版本,是本题的前置基础。对比两道题的实现可以发现:47 题只是在 46 题的
if not vis[j]基础上增加了一条去重剪枝条件,其余框架完全一致。掌握"先排序、再按值去重"的模式后,可以顺带推广到其他"含重复元素求组合/子集"类问题(如仓库中 剑指 Offer II 083/084 的全排列系列题解),去重思路一脉相承。