# 90. Subsets II | LeetCode Solution

## 90. Subsets II | LeetCode Solution

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`

class Solution
{
public:
vector<vector<int>> ans;
void helper(vector<int> &nums, vector<int> &curr, int idx)
{
ans.push_back(curr);
for (int i = idx; i < nums.size(); i++)
if (i == idx || nums[i] != nums[i - 1])
{
curr.push_back(nums[i]);
helper(nums, curr, i + 1);
curr.pop_back();
}
}

vector<vector<int>> subsetsWithDup(vector<int> &nums)
{
sort(nums.begin(), nums.end());
vector<int> curr;
helper(nums, curr, 0);
return ans;
}
};

class Solution
{
public:
vector<vector<int>> ans;
void helper(vector<int> &nums, vector<int> &curr, int idx, bool pre)
{
if (idx == nums.size())
{
ans.push_back(curr);
return;
}

helper(nums, curr, idx + 1, false);

if (idx > 0 && nums[idx] == nums[idx - 1] && !pre)
return;

curr.push_back(nums[idx]);
helper(nums, curr, idx + 1, true);
curr.pop_back();
}

vector<vector<int>> subsetsWithDup(vector<int> &nums)
{
sort(nums.begin(), nums.end());
vector<int> curr;
helper(nums, curr, 0, false);
return ans;
}
};