# Java solution using bit manipulation

• public class Solution {
public List<List<Integer>> subsetsWithDup(int[] num) {
Arrays.sort(num);
List<List<Integer>> lists = new ArrayList<>();
int subsetNum = 1<<num.length;
for(int i=0;i<subsetNum;i++){
List<Integer> list = new ArrayList<>();
boolean illegal=false;
for(int j=0;j<num.length;j++){
if((i>>j&1)==1){
if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
illegal=true;
break;
}else{
}
}
}
if(!illegal){
}

}
return lists;
}
}

The idea is using every bit to represent one element in the set. The total number is 2 to num.length. Then we need to avoid duplicates. After we sort the array, the same number will be adjacent to each other.

For example the set is {1,1,1}. We can get subset {} and {1} first. That's great.
Then we need to pay attention. Suppose we have a subset x, which including the second 1 but not the first 1, x is a duplicate.
That's why I write the predicate:
if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
illegal=true;
break;
}

Hope someone can explain it better. I will go to gym now.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.