Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Example：
Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Note：
Note: The solution set must not contain duplicate subsets.
解释下题目：
输出所有的不重复子集
1. 在078的基础上修改呗
实际耗时：44ms
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
Arrays.sort(nums);
recursion(result, temp, 0, nums);
return result;
}
public void recursion(List<List<Integer>> result, List<Integer> temp, int start, int[] nums) {
if (!result.contains(new ArrayList<>(temp))) {
result.add(new ArrayList<>(temp));
}
for (int i = start; i < nums.length; i++) {
temp.add(nums[i]);
recursion(result, temp, i + 1, nums);
temp.remove(temp.size() - 1);
}
}
踩过的坑：{4,4,4,1,4} 主要是忘了对数组进行排序
思路与078一样，只是加了重复判断
时间复杂度O(2^n)
空间复杂度O(1)
2. 在1之上进行修改
实际耗时：3ms
public void recursion2(List<List<Integer>> result, List<Integer> temp, int start, int[] nums) {
if (start <= nums.length) {
result.add(temp);
}
int i = start;
while (i < nums.length) {
temp.add(nums[i]);
recursion2(result, new ArrayList<>(temp), i + 1, nums);
temp.remove(temp.size() - 1);
i++;
while (i < nums.length && nums[i] == nums[i - 1]) {
i++;
}
}
return;
}
思路其实就是加了一个如果下一个数字和当前的数字一样，就直接跳过。
