# LeetCode 47: Permutations II

## Problem Restatement

We are given an array `nums` that may contain duplicate numbers.

We need to return all possible unique permutations in any order.

A permutation is an ordering that uses every element exactly once. Since `nums` may contain duplicates, different index choices can produce the same value ordering. We must return each unique ordering only once. The official problem states: given a collection of numbers that might contain duplicates, return all possible unique permutations in any order.

Example:

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

The unique permutations are:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` that may contain duplicates |
| Output | A list of all unique permutations |
| Rule | Each permutation uses every element exactly once |
| Order | The answer may be returned in any order |

Function shape:

```python
def permuteUnique(nums: list[int]) -> list[list[int]]:
    ...
```

## First Thought: Generate Then Deduplicate

One simple approach is to generate all permutations, then put them into a set to remove duplicates.

For example, with:

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

choosing the first `1` before the second `1` can create the same visible permutation as choosing the second `1` before the first `1`.

So a raw permutation generator may produce duplicates.

We could store each result as a tuple in a set:

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

This works, but it wastes time generating duplicate permutations.

We can avoid duplicates during the search itself.

## Key Insight

Sort the array first.

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

After sorting, equal values are adjacent.

Then during backtracking, when we see the same value as the previous index, we decide whether to skip it.

The duplicate-skipping rule is:

```python
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue
```

Meaning:

If the current value equals the previous value, and the previous copy has not been used in the current path, skip the current copy.

This forces duplicate values to be used in a stable order.

For two equal `1`s, we always choose the first `1` before the second `1` at the same decision level. That prevents duplicate permutations.

## Algorithm

Sort `nums`.

Initialize:

```python
ans = []
path = []
used = [False] * len(nums)
```

Define `backtrack()`:

1. If `len(path) == len(nums)`, append a copy of `path` to `ans`.
2. Loop through each index `i`.
3. If `used[i]` is true, skip it.
4. If `nums[i]` equals `nums[i - 1]` and the previous copy is not used, skip it.
5. Choose `nums[i]`.
6. Recurse.
7. Undo the choice.

Return `ans`.

## Walkthrough

Use:

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

After sorting:

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

Start:

```python
path = []
used = [False, False, False]
```

At the first position, we try index `0`:

```python
path = [1]
used = [True, False, False]
```

Now we can choose index `1`, because the previous duplicate is already used:

```python
path = [1, 1]
used = [True, True, False]
```

Then choose `2`:

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

Backtrack.

From:

```python
path = [1]
used = [True, False, False]
```

choose `2`:

```python
path = [1, 2]
used = [True, False, True]
```

Then choose the remaining `1`:

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

Backtrack to the empty path.

Now try index `1`.

It also has value `1`, but index `0` is not used.

The duplicate rule applies:

```python
i > 0 and nums[i] == nums[i - 1] and not used[i - 1]
```

So we skip index `1` at the first position.

Then choose index `2`:

```python
path = [2]
used = [False, False, True]
```

Then choose index `0`, then index `1`:

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

Final answer:

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

## Correctness

The algorithm only appends a result when `path` has length `len(nums)`. Since each chosen index is marked in `used`, no index can be chosen twice. Therefore every appended path uses every input element exactly once.

The loop tries every unused index as the next candidate, except when choosing that index would create a duplicate ordering.

Because the array is sorted, equal values are adjacent. The duplicate rule skips `nums[i]` when it equals `nums[i - 1]` and the previous equal value has not been used in the current path.

This means among equal values, the algorithm only allows them to be selected in their original sorted order at the same decision level. Swapping two equal values would produce the same visible permutation, so the skipped branch cannot lead to a new unique result.

Every unique permutation still remains reachable. For any value ordering, choose the equal copies from left to right whenever that value appears. This choice passes the duplicate rule and constructs the permutation.

Thus, the algorithm returns every unique permutation exactly once.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * k)` | There are `k` unique permutations, and copying each result costs `O(n)` |
| Space | `O(n)` | The recursion stack, `path`, and `used` array use linear space |

Here, `n = len(nums)` and `k` is the number of unique permutations.

The returned output itself uses `O(n * k)` space.

## Implementation

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

        ans = []
        path = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                ans.append(path[:])
                return

            for i in range(len(nums)):
                if used[i]:
                    continue

                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

                used[i] = True
                path.append(nums[i])

                backtrack()

                path.pop()
                used[i] = False

        backtrack()
        return ans
```

## Code Explanation

We sort the input first:

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

Sorting places duplicate values next to each other, which lets us detect repeated choices.

The `used` array tracks which indices are already in the current permutation:

```python
used = [False] * len(nums)
```

The base case is:

```python
if len(path) == len(nums):
```

At that point, we append a copy:

```python
ans.append(path[:])
```

We skip an index if it has already been used:

```python
if used[i]:
    continue
```

Then we skip duplicate branches:

```python
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue
```

This says: do not choose the later duplicate before the earlier duplicate at the same recursive level.

Then we choose the value:

```python
used[i] = True
path.append(nums[i])
```

After recursion, we undo the choice:

```python
path.pop()
used[i] = False
```

This restores the state for the next candidate.

## Testing

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

def run_tests():
    s = Solution()

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

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

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

    assert normalize(s.permuteUnique([0, 1, 0])) == normalize([
        [0, 0, 1],
        [0, 1, 0],
        [1, 0, 0],
    ])

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

    print("all tests passed")

run_tests()
```

| Test | Expected Count | Reason |
|---|---:|---|
| `[1, 1, 2]` | `3` | Standard duplicate case |
| `[1, 2, 3]` | `6` | No duplicates |
| `[1, 1, 1]` | `1` | All values are identical |
| `[0, 1, 0]` | `3` | Duplicate zero values |
| `[-1, 2, -1]` | `3` | Duplicate negative values |