目标
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0]
输出：[[],[0]]说明：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
思路
返回数组不重复的子序列。
枚举子序列可以使用迭代或者回溯。迭代的思路是使用 bitmap 表示对应下标是否在子序列中，如果数组中元素个数为 n，bitmap 值为 1 << n。回溯的思路是当前元素选或者不选，或者从当前元素到结尾下一个元素选哪一个。
题目的关键是如何判断收集到的子序列是否重复，这里的重复指组成子序列的元素与个数完全相同。
很容易想到使用序列的字符串来判断是否重复，但是如何处理组成元素相同而顺序不同的情况？可以对原数组排序，这样可以保证相同元素在子序列中的出现位置相同。比如 4, 4, 4, 1, 4，排序后 4 只会出现在 1 的后面，如果子序列中 4 的个数相同，那么子序列字符串也相同，这样就可以去重了。
如果使用回溯，则可以在枚举时直接去重。如果不选择某个元素，那么后面 相同的 元素都不选。这样可以保证相同元素同样的出现次数只枚举一次。
也有网友使用桶排序，回溯时对相同元素枚举取 0 ~ k 个。
代码
/**
* @date 2025-02-05 9:09
*/
public class SubsetsWithDup90 {
public List<List<Integer>> subsetsWithDup_v1(int[] nums) {
int n = nums.length;
List<List<Integer>> res = new ArrayList<>();
Set<String> set = new HashSet<>();
Arrays.sort(nums);
n = 1 << n;
for (int i = 0; i < n; i++) {
List<Integer> subset = new ArrayList<>();
for (int j = 0; j < nums.length; j++) {
if (((i >> j) & 1) == 1) {
subset.add(nums[j]);
}
}
if (!set.contains(subset.toString())) {
res.add(subset);
}
set.add(subset.toString());
}
return res;
}
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
List<Integer> subset = new ArrayList<>();
dfs(0, nums, subset, res);
return res;
}
public void dfs(int index, int[] nums, List<Integer> subset, List<List<Integer>> res) {
if (index == nums.length) {
res.add(new ArrayList<>(subset));
return;
}
subset.add(nums[index]);
dfs(index + 1, nums, subset, res);
subset.remove(subset.size() - 1);
index++;
while (index < nums.length && nums[index] == nums[index - 1]){
index++;
}
dfs(index, nums, subset, res);
}
}
性能
bitmap 迭代
回溯
