# 90. Subsets II

{% hint style="danger" %}
For this problem, `[1, 4]` and `[4, 1]` are the same subsets
{% endhint %}

### Solution:

1. Sort the list to let same numbers be neighborhood.
2. Very similar to #78. 
3. Add `if` inside the adding level process.

Time complexity = T\_mergeSort + T\_subsets =  $$O(NlgN) + O(n*2^n) = O(n*2^n)$$ 

Space complexity = $$O(n\*2^n)$$ 

{% code title="java" %}

```java
class Solution {
    public List<List<Integer>> res = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        helper(nums, new ArrayList<Integer>(), 0);
        return res;
    }
    
    public void helper(int[] nums, ArrayList<Integer> level, int i) {
        res.add(new ArrayList<Integer>(level));
        if(i == nums.length) return;
        
        for(int j = i; j < nums.length; j ++) {
            if(j > i && nums[j] == nums[j-1])
                continue;
            level.add(nums[j]);
            helper(nums, level, j + 1);
            level.remove(level.size() - 1);
        }
    }
}
```

{% endcode %}