### 题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

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],
[]
]


### 暴力回溯（具有动态规划思想），利用Set去重

[]


[]
[1]


[]
[1]
----------------
[2] -> 在[]后面插入2
[1,2] -> 在[1]后面插入2


#### 代码

public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
Set<List<Integer>> res = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
List<List<Integer>> mirror = new ArrayList<>(res);
for (List<Integer> list : mirror) {
list.remove(list.size()-1);
}
}
return new ArrayList<List<Integer>>(res);
}
}


### 遇到重复的数字只在部分元素后面插入重复数字

[]
[1]                             # 上半区
-----------------------------------------  需要记住这个分界点
[2] -> 在[]后面插入2              # 下半区
[1,2] -> 在[1]后面插入2


[]
[1]                             # 上半区
-----------------------------------------  需要记住这个分界点
[2] -> 在[]后面插入2              # 下半区
[1,2] -> 在[1]后面插入2
-----------------------------------------
[2,2] -> 对下半区元素后插入2
[1,2,2] -> 对下半区元素后插入2


#### 代码

public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0, start = 0; i < nums.length; i++) {
if (i == 0 || nums[i] != nums[i-1]) { start = 0; } // append nums[i] to each old member
int size = res.size();
for (int j = start; j < size; j++) {
List<Integer> temp = new ArrayList<>(res.get(j));