京公网安备11010502063487号给定一个可能包含重复元素的整数数组，返回它所有可能的子集（幂集），子集不能重复（[1, 2] 和 [2, 1] 只算一个，两个 2 各自被选中但内容相同的子集也只算一个）。这是第 78 题（无重复元素）的进阶，去重的办法和"组合总和 II"、"全排列 II"一脉相承：先排序，让相同的数挨在一起，然后在回溯的同一层里，遇到与前一个相同的数就跳过（同一层已经把"选这个数"的情形处理过了）。本文用真实数据展示第 78 题的写法直接用在这里会得到多少重复子集，给出五种语言的实现，并把跳过的过程做成分步演示。
完整题目见官方页面（链接在文末）。结果按集合比较（每个子集内部排序，子集之间也排序）。基准解列出所有下标的组合，取出对应的数排序后放进集合去重，与"排序加同层跳过"的回溯是两种独立的写法。一共 12 组用例，覆盖：官方两个示例、空数组、全部相同、含多种重复、没有重复：
输入 [[1,2,2]] 输出 [[],[1],[1,2],[1,2,2],[2],[2,2]] 输入 [[0]] 输出 [[],[0]] 输入 [[]] 输出 [[]] 输入 [[1,1]] 输出 [[],[1],[1,1]] 输入 [[1,1,1]] 输出 [[],[1],[1,1],[1,1,1]] 输入 [[4,4,4,1,4]] 输出 [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
第 78 题的回溯里，每个元素当作互不相同的，选不同下标的两个相同的数得到的子集内容一样，但会被当成两个不同的结点。下面是没有"同层跳过"的写法与 solve 的真实结果：
# 没有「同层相同的数跳过」的写法（第 78 题的做法直接用在有重复的数组上） [1, 2, 2]: 该写法得到 8 个（不同的只有 6 个） solve 得到 6 个 [1, 1, 1]: 该写法得到 8 个（不同的只有 4 个） solve 得到 4 个 [4, 4, 4, 1, 4]: 该写法得到 32 个（不同的只有 10 个） solve 得到 10 个 [1, 2, 3]: 该写法得到 8 个（不同的只有 8 个） solve 得到 8 个 随机 20000 组：该写法得到重复子集的有 13584 组（67.9%）
[1, 2, 2] 应该有 6 个不同的子集，直接沿用第 78 题的写法得到 8 个（其中两个是 [1, 2]，两个是 [2]）；[1, 1, 1] 应该是 4 个（空集、一个 1、两个 1、三个 1），得到 8 个；[4, 4, 4, 1, 4] 应该是 10 个，得到 32 个（2 的 5 次方）。没有重复元素的 [1, 2, 3] 两种写法一致。在随机的 20000 组数据里，这种写法得到重复子集的有 13584 组，占 67.9%。
先排序。dfs(start) 进入时先把当前路径收集一份（每个结点本身就是一个子集）；然后对 i 从 start 到末尾：如果 i > start 并且 nums[i] == nums[i - 1]，说明同一层里前一个相同的数已经作为"这一位"试过了，跳过；否则把 nums[i] 加入路径，递归 dfs(i + 1)，返回后撤销。注意条件是 i > start，而不是 i > 0：start 是这一层的起点，这一层里的第一个数不能跳过，否则 [1, 2, 2] 里选两个 2 的子集 [2, 2] 会丢掉。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): nums = sorted(nums) # 排序：让相同的数挨在一起 res, path = [], [] def dfs(start): res.append(path[:]) # 每个结点本身就是一个子集 for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: # 同一层里，相同的数只作为"这一位"试一次，否则会得到重复的子集 continue path.append(nums[i]) dfs(i + 1) path.pop() dfs(0) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,2]] → [[],[1],[1,2],[1,2,2],[2],[2,2]] [[0]] → [[],[0]] [[]] → [[]] [[1,1]] → [[],[1],[1,1]] [[1,1,1]] → [[],[1],[1,1],[1,1,1]] [[4,4,4,1,4]] → [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
Java · 解法代码class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // 排序：让相同的数挨在一起 List<List<Integer>> res = new ArrayList<>(); dfs(nums, 0, new ArrayList<>(), res); return res; } private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> res) { res.add(new ArrayList<>(path)); // 每个结点本身就是一个子集 for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1]) continue; // 同一层里，相同的数只试一次，否则会得到重复的子集 path.add(nums[i]); dfs(nums, i + 1, path, res); path.remove(path.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,2]] → [[],[1],[1,2],[1,2,2],[2],[2,2]] [[0]] → [[],[0]] [[]] → [[]] [[1,1]] → [[],[1],[1,1]] [[1,1,1]] → [[],[1],[1,1],[1,1,1]] [[4,4,4,1,4]] → [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
Go · 解法代码import "sort" func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) // 排序：让相同的数挨在一起 res := [][]int{} path := []int{} var dfs func(start int) dfs = func(start int) { res = append(res, append([]int{}, path...)) // 每个结点本身就是一个子集 for i := start; i < len(nums); i++ { if i > start && nums[i] == nums[i-1] { // 同一层里，相同的数只试一次，否则会得到重复的子集 continue } path = append(path, nums[i]) dfs(i + 1) path = path[:len(path)-1] } } dfs(0) return res }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,2]] → [[],[1],[1,2],[1,2,2],[2],[2,2]] [[0]] → [[],[0]] [[]] → [[]] [[1,1]] → [[],[1],[1,1]] [[1,1,1]] → [[],[1],[1,1],[1,1,1]] [[4,4,4,1,4]] → [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
JavaScript · 解法代码function subsetsWithDup(nums) { nums.sort((a, b) => a - b); // 排序：让相同的数挨在一起 const res = []; const path = []; const dfs = (start) => { res.push([...path]); // 每个结点本身就是一个子集 for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) continue; // 同一层里，相同的数只试一次，否则会得到重复的子集 path.push(nums[i]); dfs(i + 1); path.pop(); } }; dfs(0); return res; }
$ node run.js < cases.jsonl [[1,2,2]] → [[],[1],[1,2],[1,2,2],[2],[2,2]] [[0]] → [[],[0]] [[]] → [[]] [[1,1]] → [[],[1],[1,1]] [[1,1,1]] → [[],[1],[1,1],[1,1,1]] [[4,4,4,1,4]] → [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { void dfs(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) { res.push_back(path); // 每个结点本身就是一个子集 for (int i = start; i < (int)nums.size(); i++) { if (i > start && nums[i] == nums[i - 1]) continue; // 同一层里，相同的数只试一次，否则会得到重复的子集 path.push_back(nums[i]); dfs(nums, i + 1, path, res); path.pop_back(); } } public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); // 排序：让相同的数挨在一起 vector<vector<int>> res; vector<int> path; dfs(nums, 0, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,2]] → [[],[1],[1,2],[1,2,2],[2],[2,2]] [[0]] → [[],[0]] [[]] → [[]] [[1,1]] → [[],[1],[1,1]] [[1,1,1]] → [[],[1],[1,1],[1,1,1]] [[4,4,4,1,4]] → [[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和"列出所有下标组合再去重"做了随机对拍：长度 0 到 9、取值 0 到 3（重复值很多）：
随机对拍 5000 组（长度 0 到 9、取值 0 到 3 的随机数组（重复值很多）；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题的输出规模随重复情况变化，耗时由输出规模决定，所以没有另做规模对比实验。
下面的演示用官方示例 [1, 2, 2]（已经有序）。深度优先地走：空集 → [1] → [1, 2] → [1, 2, 2]；回退到 [1] 这一层，下一个是下标 2 的 2，它与同一层前一个（下标 1 的 2）相同，被跳过（淡色）；再回退到根，选下标 1 的 2 得到 [2]，继续得到 [2, 2]；最后根这一层的下标 2 的 2 同样被跳过。共 6 个子集。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的子集集合与 solve 的返回值一致。