“给定一个整数数组,返回该数组所有可能的子集,解集不能包含重复的元素。”
题目链接:
来源:力扣(LeetCode)
链接:90. 子集 II - 力扣(LeetCode) (leetcode-cn.com)
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入: nums = [1,2,2]
输出: [[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入: nums = [0]
输出: [[],[0]]
本题根据78题【子集】改进而来,可以先再复习一下78题解法,再来看这道题。
对于这道题来说,可以使用迭代进行子集的枚举,但是需要避免重复的子集。
对于当前数组来说,如果当前选择的数x有与其相同的数y,并且没有选择y,那么此时包含x的子集,必然会出现包含y的所有子集中。
对于上述起那个框,可以先将数组排序,然后判断当前数组与上一个数相同,就可以跳过当前生成的子集,就可以避免重复子集。
代码参考:
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
boolean flag = true;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
flag = false;
break;
}
t.add(nums[i]);
}
}
if (flag) {
ans.add(new ArrayList<Integer>(t));
}
}
return ans;
}
}
时间复杂度 : O(n x 2n)
其中n是数组的长度,排序时间复杂度为O(n log n),一共有2n个状态,每个状态需要O(n)的时间来构造,所以是 O(n x 2n)。
空间复杂度: O(n)
其中n是数组的长度,只需要使用一个临时数组n的空间即可。
对于子集的问题,使用回溯算法是一种很好的方法。
回溯算法是深度优先遍历算法,对于子集问题,排列问题而言,不计较一个组合内元素的顺序性。