# My accepted Java solution

• The idea is to maintain a separate list of subsets, newList, to keep track of all the newly added subsets at the last step in the for loop. If num[i] == num[i - 1], we don't want to append num[i] to all existing subsets but just to the ones that just got added last round to prevent duplication.

For example, we have num to be {1, 2, 2}

1. For {1}, we have subsets {{ }, {1}}.
2. For {1, 2}, we have subsets{{ }, {1}, {2}, {1, 2}}. We just add {2} and {1, 2} to the subsets. So newList is {{2}, {1, 2}}.
3. For {1, 2, 2}, since 2 == 2, we only append 2 to {2} and {1, 2} in newList respectively, which gives us a new newList {{2, 2}, {1, 2, 2}}, and then we add all to the subsets, so the result is {{ }, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}}.

Please comment if you see something wrong or can be improved. Cheers!

``````public class Solution {
public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subset = new ArrayList<Integer>();

if (num.length == 0) {
return result;
}

Arrays.sort(num);

List<List<Integer>> newList = new ArrayList<List<Integer>>();
subset = new ArrayList<Integer>();
for (int i = 1; i < num.length; i++) {
if (num[i] == num[i - 1]) {
List<List<Integer>> nextList = new ArrayList<List<Integer>>();
for (List<Integer> li : newList) {
subset = new ArrayList<Integer>(li);
}
newList = nextList;
}
else {
newList.clear();
for (List<Integer> li : result) {
subset = new ArrayList<Integer>(li);
}
}
}
return result;
}
}``````

• How about using a HashSet and then convert it to List?

• Using hashSet is the first idea i come up with but it seems to be a waste of space.

• yes, this solution is better than use hashset, have save a lot of space

• have two questions. 1st: when do you add{} to subset? 2nd: ex, if we have {0,1}, so expected output will be {{},{0},{1},{0,1}}. But in the for loop especially else part for this example, I think it only add{1} to the result list, where is part of code of adding {0,1}?? Since for loop only loop 1 time(i=1,num size is 2),so I cant find the part that adding {0,1} to the subset. Can you give me some idea about it? Thanks

• You can also use .contains() instead of HashSet

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