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:

nums = [1, 1, 2]

The unique permutations are:

[
    [1, 1, 2],
    [1, 2, 1],
    [2, 1, 1],
]

Input and Output

Function shape:

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:

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:

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.

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:

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 1s, we always choose the first 1 before the second 1 at the same decision level. That prevents duplicate permutations.

Algorithm

Sort nums.

Initialize:

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:

nums = [1, 1, 2]

After sorting:

[1, 1, 2]

Start:

path = []
used = [False, False, False]

At the first position, we try index 0:

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

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

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

Then choose 2:

[1, 1, 2]

Backtrack.

From:

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

choose 2:

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

Then choose the remaining 1:

[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:

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:

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

Then choose index 0, then index 1:

[2, 1, 1]

Final answer:

[
    [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

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

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

Implementation

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:

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:

used = [False] * len(nums)

The base case is:

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

At that point, we append a copy:

ans.append(path[:])

We skip an index if it has already been used:

if used[i]:
    continue

Then we skip duplicate branches:

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:

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

After recursion, we undo the choice:

path.pop()
used[i] = False

This restores the state for the next candidate.

Testing

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()