京公网安备11010502063487号给定一个可能有重复元素的数组，返回所有不重复的全排列。相比上一题，多了去重：[1, 1, 2] 有 6 种排法，但只有 3 种不同的排列。做法是先排序，让相同的数挨在一起，然后规定：相同的数字必须按下标顺序使用，也就是当前的数字如果与前一个相同，而前一个在这一层还没被用过，就跳过它。本文用真实数据对比不去重、以及去重条件的两种写法（not used[i-1] 和 used[i-1]），实测递归调用次数，给出五种语言的实现，并把跳过的过程做成分步演示。
完整题目见官方页面（链接在文末）。结果按集合比较。基准解是 set(itertools.permutations(nums))：先生成所有排列（包含重复），再用集合去重，最后排序，是与回溯完全不同的写法。一共 12 组用例，覆盖：官方示例、没有重复、全部相同、重复的值成对出现、重复的值出现三次或四次：
输入 [[1,1,2]] 输出 [[1,1,2],[1,2,1],[2,1,1]] 输入 [[1,2,3]] 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 输入 [[1]] 输出 [[1]] 输入 [[1,1]] 输出 [[1,1]] 输入 [[1,1,1]] 输出 [[1,1,1]] 输入 [[2,2,1,1]] 输出 [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
去重的关键是"相同的数字要按固定的顺序使用"。有两种写法：当前的数与前一个相同，并且前一个没被使用（not used[i-1]）时跳过；或者前一个已被使用（used[i-1]）时跳过。这两种写法都能得到正确的结果，但剪枝的时机不同。下面是不去重、以及两种写法的真实结果，包括递归调用次数：
三种写法：不去重 / 跳过条件写成 not used[i-1]（本文）/ 跳过条件写成 used[i-1] 输入 | 不去重的结果个数 | not used[i-1] 结果个数、递归调用次数 | used[i-1] 结果个数、递归调用次数 | 正确的不同排列数 [1, 1, 2]: 6 | 3（正确）、9 次 | 3（正确）、12 次 | 3 [1, 1, 2, 2]: 24 | 6（正确）、19 次 | 6（正确）、33 次 | 6 [1, 1, 1, 2, 2]: 120 | 10（正确）、34 次 | 10（正确）、99 次 | 10 [1, 1, 2, 2, 3, 3]: 720 | 90（正确）、271 次 | 90（正确）、550 次 | 90 [1, 1, 1, 1, 2, 2, 2]: 5040 | 35（正确）、125 次 | 35（正确）、1192 次 | 35
不去重的写法得到 n! 个结果（[1, 1, 2] 得到 6 个而不是 3 个，[1, 1, 1, 1, 2, 2, 2] 得到 5040 个而不是 35 个）。两种去重写法的结果个数都等于正确的不同排列数，但递归次数不同：not used[i-1] 更早地剪掉重复的分支，[1, 1, 1, 1, 2, 2, 2] 上只需要 125 次调用，used[i-1] 写法需要 1192 次，约 9.5 倍。所以本文采用 not used[i-1]。这里的比较只覆盖了这 5 组输入，没有推广到一般结论。
先排序。dfs() 与上一题相同，只在循环里多一个判断：i > 0 且 nums[i] == nums[i-1] 且 !used[i-1] 就跳过。直观理解：如果前一个相同的数在当前路径里还没被选，说明这条路径是从"先选后一个、后选前一个"的顺序来的，这种顺序在"先选前一个"的分支里已经覆盖过了。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): nums = sorted(nums) # 排序：相同的数挨在一起 res, path = [], [] used = [False] * len(nums) def dfs(): if len(path) == len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue # 相同的数必须按下标顺序使用：前一个还没用，就不能先用后一个 used[i] = True path.append(nums[i]) dfs() path.pop() used[i] = False dfs() return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,1,2]] → [[1,1,2],[1,2,1],[2,1,1]] [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1]] → [[1]] [[1,1]] → [[1,1]] [[1,1,1]] → [[1,1,1]] [[2,2,1,1]] → [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
Java · 解法代码class Solution { public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); // 排序：相同的数挨在一起 List<List<Integer>> res = new ArrayList<>(); dfs(nums, new boolean[nums.length], new ArrayList<>(), res); return res; } private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) { if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 相同的数必须按下标顺序使用 used[i] = true; path.add(nums[i]); dfs(nums, used, path, res); path.remove(path.size() - 1); used[i] = false; } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,1,2]] → [[1,1,2],[1,2,1],[2,1,1]] [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1]] → [[1]] [[1,1]] → [[1,1]] [[1,1,1]] → [[1,1,1]] [[2,2,1,1]] → [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
Go · 解法代码import "sort" func permuteUnique(nums []int) [][]int { sort.Ints(nums) // 排序：相同的数挨在一起 res := [][]int{} path := []int{} used := make([]bool, len(nums)) var dfs func() dfs = func() { if len(path) == len(nums) { res = append(res, append([]int{}, path...)) return } for i := range nums { if used[i] { continue } if i > 0 && nums[i] == nums[i-1] && !used[i-1] { // 相同的数必须按下标顺序使用 continue } used[i] = true path = append(path, nums[i]) dfs() path = path[:len(path)-1] used[i] = false } } dfs() return res }
$ go build -o bin . && ./bin < cases.jsonl [[1,1,2]] → [[1,1,2],[1,2,1],[2,1,1]] [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1]] → [[1]] [[1,1]] → [[1,1]] [[1,1,1]] → [[1,1,1]] [[2,2,1,1]] → [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
JavaScript · 解法代码function permuteUnique(nums) { nums.sort((a, b) => a - b); // 排序：相同的数挨在一起 const res = []; const path = []; const used = new Array(nums.length).fill(false); const dfs = () => { if (path.length === nums.length) { res.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // 相同的数必须按下标顺序使用 used[i] = true; path.push(nums[i]); dfs(); path.pop(); used[i] = false; } }; dfs(); return res; }
$ node run.js < cases.jsonl [[1,1,2]] → [[1,1,2],[1,2,1],[2,1,1]] [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1]] → [[1]] [[1,1]] → [[1,1]] [[1,1,1]] → [[1,1,1]] [[2,2,1,1]] → [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) { if (path.size() == nums.size()) { res.push_back(path); return; } for (int i = 0; i < (int)nums.size(); i++) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 相同的数必须按下标顺序使用 used[i] = true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); used[i] = false; } } public: vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); // 排序：相同的数挨在一起 vector<vector<int>> res; vector<bool> used(nums.size(), false); vector<int> path; dfs(nums, used, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,1,2]] → [[1,1,2],[1,2,1],[2,1,1]] [[1,2,3]] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] [[1]] → [[1]] [[1,1]] → [[1,1]] [[1,1,1]] → [[1,1,1]] [[2,2,1,1]] → [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
每个值出现两次的数组（0,0,1,1,2,2…），n 为 4、6、8、10，每个规模取三次中最快的一次：
元素个数 n（每个值出现 2 次） | 暴力解 | 本文解法
4 | 0.005 ms | 0.005 ms
6 | 0.059 ms | 0.062 ms
8 | 3.228 ms | 1.739 ms
10 | （未测，太慢） | 85.928 msn = 8 时，回溯（1.74ms）比"先生成所有排列再集合去重"（3.23ms）快约 1.9 倍，因为后者要生成 40320 个排列再去重，而回溯只生成 2520 个不同的排列。n = 10 时基准没有再测，回溯需要 85.9ms。
Python 版本另外和基准解做了随机对拍，长度 1 到 7，取值 0 到 3，重复值很多：
随机对拍 5000 组（长度 1 到 7、取值 0 到 3 的随机数组（重复值很多）；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 [1, 1, 2]。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的排列集合与 solve 的返回值一致。注意：第一层里，选了下标 0 的 1 之后，下标 1 的 1 也可以选（前一个已经被用了，在当前路径里）；但如果从第一层直接选下标 1 的 1（而下标 0 的还没用），就会被跳过。