### Subsets II

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

``````import java.util.*;
/**
* Created by gzdaijie on 16/6/4
* 对于每一位数字,每个子集可以选择包含或不包含
* 对于重复的数字,特殊处理,即看作是一个整体.
* 例如1,2,2 处理到2时,有三种情况,包含[],包含[2],包含[2,2]共三种情况
*/
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
int[] flag = new int[nums.length];

Arrays.sort(nums);

/**
* 移除nums中重复的数字,flag记录每个位置数字出现的次数
*/
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == nums[k]) {
flag[k]++;
} else {
flag[++k] = 1;
nums[k] = nums[i];
}
}

/**
* 对于k个数,每个子集选择包含或不包含
* 一个数字如果出现了j次,那么就有j+1种包含的可能,分别是[],[x],[x,x],[x...x]
*/
for (int i = 0; i <= k; i++) {
int size = result.size();
while (size-- > 0) {
List<Integer> top = result.poll();
List<Integer> top_copy;
for (int j = 0; j < flag[i]; j++) {
top_copy =  (List<Integer>) ((ArrayList<Integer>) top).clone();

for (int l = 0; l <= j; l++) top_copy.add(nums[i]);