# My solution using bit masks

• Here is my solution using bit masks.

``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] num) {
//Sort the input
Arrays.sort(num);
int numberSets = 1 << num.length;
List<List<Integer>> solution = new LinkedList<>();
for(int i = 0; i<numberSets; i++){
List<Integer> subset = new LinkedList<Integer>();
for(int j = 0; j< num.length; j++){
if((i & (1 << j)) > 0){
}
}
if(!solution.contains(subset))
}

return solution;
}
``````

}

• ``````if(!solution.contains(subset))
``````

This is too slow.

• ``````class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
int n = S.size();
vector <vector <int> > res;
for (int i = 0; i < (1 << n); i++) {
vector <int> cur;
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) {
cur.push_back(S[j]);
}
}
sort(cur.begin(), cur.end());
res.push_back(cur);
}
sort(res.begin(), res.end());
res.resize(unique(res.begin(), res.end()) - res.begin());
sort(res.rbegin(), res.rend());
return res;
}
};
``````

Same idea but with sorting and eliminating duplicates.

O(2^n * n) instead of O(2^n * n * 2^n)

• You can use `Set<List<Integer>>` instead of `List<List<Integer>>` to speed up checking for duplicate subsets.

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