# [LeetCode 90] Subsets II

### Question

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

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = `[1,2,2]`, a solution is:

```[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
```

### Stats

 Frequency 2 Difficulty 4 Adjusted Difficulty 3 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This is a question based on “Subsets” question.

Solution is similar, only need to add features to avoid duplication.

### Solution

Based on the solution of previous question, I only add 1 variable called nonDupSize, which is the size that I need to merge new element with. For example, input = {1, 2, 3, 3}

Initialize the subset: {}

Added element “1”: {}, {“1”} (1 more elements)

Added element “2”: {}, {“1”}, {“2”}, {“1”, “2”} (2 more elements)

Added element “3”: {}, {“1”}, {“2”}, {“1”, “2”}, {“3”}, {“1”,“3”}, {“2”,“3”}, {“1”, “2”,“3”} (4 more elements)

Added element “3”: {}, {“1”}, {“2”}, {“1”, “2”}, {“3”}, {“1”,“3”}, {“2”,“3”}, {“1”,“2”,“3”}, {“3”,“3”}, {“1”,“3”,“3”}, {“2”,“3”,“3”}, {“1”,“2”,“3”,“3”} (4 more elements)

So instead of getting every list and merge with new element, I only get the lists of pre-calculated size (from bottom), and merge. Someone is having similar solution using a start-pointer.

### Code

my code

``````public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
// In this solution I introduce a new variable: nonDupSize
int curSize = 1, nonDupSize = 1;
for (int i = 0; i < num.length; i ++) {
curSize = ans.size();
if (i > 0 && num[i] != num[i - 1]) nonDupSize = curSize;
for (int j = curSize - nonDupSize; j < curSize; j ++) {
ArrayList<Integer> cur = new ArrayList<Integer>(ans.get(j));
}
}
return ans;
}
``````

Updated on June 12th - solution using the ‘Permutation Model’.

``````public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(num == null || num.length == 0) {
return result;
}
Arrays.sort(num);
return result;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int position) {