题目
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
答案
效率低的答案(sort subsets):
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Set<List<Integer>> set_of_lists = new HashSet<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
subsets(nums, set_of_lists, list, 0);
return new ArrayList<List<Integer>>(set_of_lists);
}
public void subsets(int[] nums, Set<List<Integer>> set_of_lists, List<Integer> curr_list, int curr_index) {
if(curr_index == nums.length) {
List<Integer> newlist = new ArrayList<Integer>(curr_list);
Collections.sort(newlist);
set_of_lists.add(newlist);
return;
}
curr_list.add(nums[curr_index]);
subsets(nums, set_of_lists, curr_list, curr_index + 1);
curr_list.remove(curr_list.size() - 1);
subsets(nums, set_of_lists, curr_list, curr_index + 1);
}
}
效率低的答案(sort nums then find subsets):
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Set<List<Integer>> set_of_lists = new HashSet<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
subsets(nums, set_of_lists, list, 0);
return new ArrayList<List<Integer>>(set_of_lists);
}
public void subsets(int[] nums, Set<List<Integer>> set_of_lists, List<Integer> curr_list, int curr_index) {
if(curr_index == nums.length) {
List<Integer> newlist = new ArrayList<Integer>(curr_list);
set_of_lists.add(newlist);
return;
}
curr_list.add(nums[curr_index]);
subsets(nums, set_of_lists, curr_list, curr_index + 1);
curr_list.remove(curr_list.size() - 1);
subsets(nums, set_of_lists, curr_list, curr_index + 1);
}
}
效率高的答案:
这个答案是从Subset第一题(本题是Subset II)改来的
由于产生duplicates的源头是相同的数字把自己append到前面产生的n个list上,所以只要确保这样的append操作不发生超过1次就好了
举个例子
树状图中第4列由于2加到了[]后面形成了[2],这样就会跟第三列的[2] 重复
避免这种情况!
image.png
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
ans.add(new ArrayList<Integer>());
int size = 0, start;
for(int i = 0; i < nums.length; i++) {
start = (i > 0 && nums[i] == nums[i - 1]) ? size : 0;
size = ans.size();
for(int j = start; j < size; j++) {
List<Integer> subset = new ArrayList<>(ans.get(j));
subset.add(nums[i]);
ans.add(subset);
}
}
return ans;
}
}