# Subsets II

Medium

Given an integer array `nums` that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

```Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
```

Example 2:

```Input: nums = [0]
Output: [[],[0]]
```

Constraints:

• `1 <= nums.length <= 10`
• `-10 <= nums[i] <= 10`

Implementation

```class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums == null || nums.length == 0){
return result;
}
List<Integer> current = new ArrayList<>();
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
subsetsWithDup(nums, result, current, used, 0);
return result;
}

private void subsetsWithDup(int[] nums, List<List<Integer>> result, List<Integer>
current, boolean[] used, int start){
for(int i = start ; i< nums.length ; i++){
if( i > start && nums[i] == nums[i-1] && !used[i-1]){
continue;
}
used[i] = true;
subsetsWithDup(nums, result, current, used, i+1);
used[i] = false;
current.remove(current.size() - 1);
}
}
}
```

Complexity Analysis

• Time Complexity: `O(N × 2N)`. 2N to generate all subsets and then `O(N)` to copy each set into output list.
• Space Complexity: `O(N × 2N)`  to keep all the subsets of length  `N``,` since each of `N `elements could be present or absent.

Categories: Backtracking

Tagged as: ,