题目描述
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
样例
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
输入:nums = [0]
输出:[[],[0]]
算法1
(DFS + 回溯) $O(n * 2^n)$
强烈建议先做了LeetCode 的46,47,78 再来做这题。
这题和47 的思想是一样的。主要是考虑在哪个位置上不需要再进行递归。如果当前的数和上一个数是相同的话,那么排列出来的数在上一个数排列出来的时候就已经全部包含了。
比如:[1,1,2,3] 以第一个1 作为开头的子集: [1],[1,2],[1,3],[1,1,2],[1,1,3],[1,2,3]
以第二个1 作为开头的子集: [1],[1,2],[1,3],[1,2,3] ,所以以第一个1 开头的子集答案中已经包含了第二个1 作为开头的子集答案,所以当遍历到第一个1 后面相同的1 时,跳过即可(剪枝)。
但这也有一个前提:nums 数组是要有序的,所以在递归之前需要对nums 数组进行排序
时间复杂度
每个值都有两种状态,即2^n,因为有n 个值,所以总的时间复杂度:O(n * 2^n)
参考文献
Java 代码
public class 子集II {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums.length == 0) return res;
path = new ArrayList<>();
Arrays.sort(nums);
dfs(0,nums);
return res;
}
void dfs(int index,int[] nums){
res.add(new ArrayList<>(path));
for(int i = index; i < nums.length; i++){
//i > index && nums[i] == nums[i-1]: 判断在i 索引以后的值是否等于i 索引的值
if(i > index && nums[i] == nums[i-1]){
continue;
}
path.add(nums[i]);
dfs(i+1,nums);
path.remove(path.size()-1);
}
}
}