# LeetCode 90: Subsets II

## Problem Restatement

We are given an integer array `nums`.

Unlike LeetCode 78, this array may contain duplicate values.

We need to return all possible subsets, also called the power set.

The answer must not contain duplicate subsets.

The subsets may be returned in any order.

The official statement says that `nums` may contain duplicates, the solution set must not contain duplicate subsets, and the constraints are `1 <= nums.length <= 10` and `-10 <= nums[i] <= 10`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | A list of unique subsets |
| Duplicate input values | Allowed |
| Duplicate output subsets | Not allowed |
| Order | The answer may be returned in any order |

Function shape:

```python
class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        ...
```

## Examples

Example 1:

```python
nums = [1, 2, 2]
```

All unique subsets are:

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

We include `[1, 2]` only once, even though there are two `2` values in the input.

Example 2:

```python
nums = [0]
```

The possible subsets are:

```python
[
    [],
    [0],
]
```

Example 3:

```python
nums = [1, 1]
```

The unique subsets are:

```python
[
    [],
    [1],
    [1, 1],
]
```

Without duplicate handling, `[1]` would be generated twice.

## First Thought: Generate Everything, Then Deduplicate

A simple method is to generate all subsets using normal backtracking, then store each subset in a set.

Because lists cannot be stored directly in a set, we would convert each subset into a tuple.

```python
seen = set()
seen.add(tuple(path))
```

This works, but it is not ideal.

It generates duplicate work first, then removes duplicates afterward.

We can avoid duplicate subsets during generation.

## Key Insight

Sort the array first.

```python
nums.sort()
```

Sorting groups equal values together.

For example:

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

becomes:

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

Now duplicates are adjacent.

During backtracking, at the same recursion level, if we already tried one value, we should skip later copies of the same value.

The key rule is:

```python
if i > start and nums[i] == nums[i - 1]:
    continue
```

This means:

If this is not the first candidate at the current level, and it equals the previous candidate, skip it.

## Why the Skip Rule Works

Use:

```python
nums = [1, 2, 2]
```

At the top level, possible first choices are:

```python
1
2
2
```

The two `2` choices would both create the same family of subsets:

```python
[2]
[2, 2]
```

So at the same recursion level, we only allow the first `2`.

However, after choosing one `2`, we are allowed to choose the next `2` deeper in the recursion.

That is how we still generate:

```python
[2, 2]
```

The distinction is important:

| Situation | Action |
|---|---|
| Same value at the same recursion level | Skip duplicate |
| Same value deeper after choosing the first copy | Allow it |

## Algorithm

1. Sort `nums`.
2. Create an empty answer list `ans`.
3. Create an empty current subset `path`.
4. Define `backtrack(start)`.
5. At the start of every call, copy `path` into `ans`.
6. Loop `i` from `start` to the end of `nums`.
7. If `nums[i]` duplicates the previous value at the same level, skip it.
8. Otherwise, choose `nums[i]`, recurse with `i + 1`, then undo the choice.
9. Return `ans`.

## Walkthrough

Use:

```python
nums = [1, 2, 2]
```

After sorting:

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

Start with:

```python
path = []
```

Record:

```python
[]
```

Choose `1`:

```python
path = [1]
```

Record:

```python
[1]
```

From here, choose the first `2`:

```python
path = [1, 2]
```

Record:

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

Choose the second `2` deeper:

```python
path = [1, 2, 2]
```

Record:

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

Backtrack to:

```python
path = [1]
```

At the same level, the second `2` is skipped because it would create another `[1, 2]`.

Backtrack to:

```python
path = []
```

Choose the first `2`:

```python
path = [2]
```

Record:

```python
[2]
```

Then choose the second `2` deeper:

```python
path = [2, 2]
```

Record:

```python
[2, 2]
```

At the top level, the second `2` is skipped.

Final answer:

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

## Correctness

The algorithm records `path` at every recursive call. Since `path` is formed by choosing elements from increasing indices, every recorded `path` is a valid subset of `nums`.

Sorting places equal values next to each other. At each recursion level, the loop tries possible next values from left to right. If `nums[i] == nums[i - 1]` and `i > start`, then choosing `nums[i]` as the next value would produce the same subsets as choosing `nums[i - 1]` as the next value at that same level. Skipping it prevents duplicate subsets.

The algorithm still allows duplicates when they are chosen at different recursion depths. For example, it can choose the first `2`, recurse, then choose the second `2`, producing `[2, 2]`. So valid subsets that need repeated values are not lost.

Every unique subset can be represented by choosing some count of each distinct value. Because the sorted array groups equal values together, the algorithm can choose the first `c` copies of a value to represent choosing that value `c` times. Therefore, every unique subset has one valid path in the recursion.

Thus the algorithm generates every unique subset exactly once.

## Complexity

Let:

```python
n = len(nums)
```

There can be up to `2^n` unique subsets when all values are distinct.

Copying each subset can cost up to `O(n)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * 2^n)` | Generate and copy up to `2^n` subsets |
| Extra space | `O(n)` | Recursion stack and current `path` |
| Output space | `O(n * 2^n)` | The answer stores all subsets |

Sorting costs `O(n log n)`, which is dominated by `O(n * 2^n)` for subset generation.

## Implementation

```python
class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()

        ans = []
        path = []

        def backtrack(start: int) -> None:
            ans.append(path.copy())

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue

                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return ans
```

## Code Explanation

Sort first so duplicate values are adjacent:

```python
nums.sort()
```

The result list is:

```python
ans = []
```

The current subset is:

```python
path = []
```

At every recursive call, record the current subset:

```python
ans.append(path.copy())
```

This is correct because every partial path is itself a valid subset.

Then try every possible next element:

```python
for i in range(start, len(nums)):
```

Skip duplicate choices at the same recursion level:

```python
if i > start and nums[i] == nums[i - 1]:
    continue
```

Choose the current number:

```python
path.append(nums[i])
```

Recurse using only later indices:

```python
backtrack(i + 1)
```

Undo the choice:

```python
path.pop()
```

Finally, return all recorded subsets.

## Testing

Because LeetCode accepts any order, normalize the result before comparing.

```python
def normalize(result):
    return sorted(tuple(row) for row in result)

def run_tests():
    s = Solution()

    assert normalize(s.subsetsWithDup([1, 2, 2])) == normalize([
        [],
        [1],
        [1, 2],
        [1, 2, 2],
        [2],
        [2, 2],
    ])

    assert normalize(s.subsetsWithDup([0])) == normalize([
        [],
        [0],
    ])

    assert normalize(s.subsetsWithDup([1, 1])) == normalize([
        [],
        [1],
        [1, 1],
    ])

    assert normalize(s.subsetsWithDup([2, 1, 2])) == normalize([
        [],
        [1],
        [1, 2],
        [1, 2, 2],
        [2],
        [2, 2],
    ])

    assert normalize(s.subsetsWithDup([1, 1, 1])) == normalize([
        [],
        [1],
        [1, 1],
        [1, 1, 1],
    ])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 2]` | Main example |
| `[0]` | Smallest shape |
| `[1, 1]` | Duplicate value only |
| `[2, 1, 2]` | Confirms sorting before backtracking |
| `[1, 1, 1]` | Multiple copies of one value |