Permutations II

When nums = [1, 1, 2], ordinary permutation backtracking treats the two 1 values as different input positions. That creates duplicate value sequences.

The fix is precise: sort the input, track used indices, and skip an equal value only when its previous equal occurrence is still unused at the current recursion depth.

The duplicate-branch problem

The contract is:

• Use every input element exactly once.
• Return every distinct value sequence.
• Return no duplicate permutations.
• Output order does not matter.

The constraints are small:

• 1 <= len(nums) <= 8
• -10 <= nums[i] <= 10

With distinct values, the usual permutation search works:

1. Choose any unused index.
2. Add its value to the current path.
3. Recurse.
4. Undo the choice.

The path and used state are still correct when values repeat. The missing piece is duplicate control.

For [1, 1, 2], the distinct outputs are:

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

If the two 1s are treated as unrelated branches, the search can construct [1, 1, 2] twice:

• choose the first 1, then the second 1, then 2
• choose the second 1, then the first 1, then 2

The index paths differ. The value sequences do not.

Generating every index-based permutation and putting the completed lists into a set would remove the final duplicates, but it wastes search work and memory. The better approach removes equivalent branches before they grow.

Equal choices are interchangeable at one depth

Think of each recursion depth as filling one position in the output permutation.

At a particular depth, the loop asks:

Which unused input value should fill this position?

After sorting, equal values sit next to each other. For [1, 1, 2], the candidates at the root are:

index:  0  1  2
value:  1  1  2

At the root, choosing index 0 with value 1 and choosing index 1 with value 1 create the same first value: [1].

They also leave the same multiset of values available: one 1 and one 2.

So the second root-level 1 is redundant. Explore the first equal occurrence and skip the later one.

This is same-depth duplicate skipping.

But the rule is local to a recursion depth. Equal values at different depths are still necessary.

After choosing index 0 with value 1, the path is:

[1]

Now index 1, also containing 1, is allowed. It produces:

[1, 1]

That second 1 is no longer competing with the first 1 for the same output position. It is filling a later position.

This distinction is the entire problem:

Equal values are interchangeable when competing for the same position. They remain usable when one equal value has already been placed earlier in the current path.

The canonical rule is:

At each recursion depth, use the earliest available occurrence of an equal value before considering later equal occurrences.

Derive the state and transition

Sort nums first:

nums.sort()

Sorting does not remove duplicates. It exposes them so adjacent values can be compared.

The search needs three pieces of state:

• path: the current value prefix.
• used[i]: whether input index i is already present in path.
• len(path): the next output position to fill.

At each depth, inspect every input index i.

1. Reject an already-used index

If used[i] is true, that input occurrence is already in the path and cannot be selected again.

if used[i]:
    continue

This tracks occurrences, not merely values. That matters because [1, 1, 2] contains two separate usable copies of 1.

2. Reject a same-depth duplicate

The duplicate condition is:

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

Read it in parts:

• i > 0: there is a previous index to compare.
• nums[i] == nums[i - 1]: the values are equal.
• not used[i - 1]: the previous equal occurrence has not already been placed in the current path.

When all three are true, the previous equal value is available to start the same branch at this depth. The current value would create an equivalent prefix, so skip it.

The final condition is the subtle one.

Suppose nums = [1, 1, 2] and the current path is [1], created by using index 0. At the next depth:

• index 1 contains an equal 1
• used[0] is true

Therefore the duplicate condition is false. Index 1 is allowed, and [1, 1] can be built.

A compact decision table helps:

The algorithm is therefore:

sort nums
create used with one flag per index
create an empty path

at each depth:
    for every index i:
        skip if index i is used
        skip if i repeats an equal unused predecessor
        mark i used
        append nums[i]
        recurse
        remove nums[i]
        unmark i

The skip is level-local. That is why repeated values can still appear in a permutation.

Why the search returns each permutation once

A passing example is useful, but an interview solution also needs a correctness argument.

Maintain this invariant at every recursive call:

path is a valid prefix of a permutation, used identifies exactly the input indices represented in path, and no equivalent value-prefix has already started at this depth.

Uniqueness

Consider two branches that first differ at a recursion depth where they choose equal values.

For example, one branch chooses index 0 containing 1, and another chooses index 1 containing 1, while both are unused.

Those branches produce:

• the same value at the current position
• the same value-prefix
• the same remaining multiset of input values

They can generate exactly the same value permutations below that point. The later equal branch adds no new output, so skipping it cannot remove a distinct permutation.

The condition not used[i - 1] ensures that only interchangeable sibling choices are removed.

Completeness

Now take any valid distinct permutation of the input values.

At each position, choose the earliest still-available input occurrence with the required value. Because the input is sorted, any earlier equal occurrence is either:

• already used in the current path, or
• not available for this intended arrangement because the canonical earlier occurrence was selected instead.

For the chosen earliest occurrence, the duplicate condition cannot incorrectly skip it. If its predecessor is equal, that predecessor has already been used, so used[i - 1] is true. If the predecessor is not equal, the equality test fails.

Therefore every distinct value permutation has at least one surviving path.

Sorting exposes equal values. The level-local rule chooses one canonical representative for equivalent branches. Together, they give both uniqueness and completeness.

For intuition, if a value appears f times, the number of distinct permutations is reduced by the repeated arrangements of those equal copies. With frequencies f1, f2, ..., the count is:

[ \frac{n!}{f_1! f_2! \cdots} ]

That formula predicts the number of leaves. The backtracking rule is what enumerates those leaves without repeating them.

Dry-run: [1, 1, 2]

The sorted input is already:

nums = [1, 1, 2]

At the root, the path is empty and every index is unused.

Root choices

• i = 0, value 1: allow it.
• i = 1, value 1: skip it because nums[1] == nums[0] and used[0] is false.
• i = 2, value 2: allow it.

The rejected branch beginning with index 1 would begin with the same value-prefix as the branch beginning with index 0. It is redundant.

Branch beginning with index 0

The path is now:

[1]

The state is:

used = [True, False, False]

At this depth:

• i = 0 is already used.
• i = 1 is an equal 1, but used[0] is true, so it is allowed.
• i = 2 with value 2 is also allowed.

Choosing index 1 gives:

[1, 1]

The only remaining value is 2, producing:

[1, 1, 2]

Backtrack to [1], then choose index 2:

[1, 2]

The remaining unused value is the second 1, producing:

[1, 2, 1]

Branch beginning with 2

At the root, choosing index 2 produces:

[2]

The remaining values are 1 and 1. The first 1 is selected, then the second 1 is allowed at the next depth because its predecessor is now used:

[2, 1, 1]

The final output is:

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

Two quick checks expose common mistakes:

• [2, 2]: the first 2 is explored; the second root-level 2 is skipped. The result contains one permutation.
• [1, 2, 3]: no adjacent values are equal, so the duplicate rule skips nothing. The ordinary permutation search remains intact.

Python implementation

from typing import List


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

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

        def dfs() -> None:
            if len(path) == len(nums):
                # path is mutated during backtracking, so store a copy.
                result.append(path.copy())
                return

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

                # Equal values may start only one branch at this depth.
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue

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

                dfs()

                path.pop()
                used[i] = False

        dfs()
        return result

Each state variable has a direct obligation:

• nums.sort() makes equal values adjacent.
• used enforces “use each input occurrence once.”
• path records the current permutation prefix.
• path.copy() preserves a completed result before path changes.
• path.pop() removes the choice made by the current call.
• used[i] = False makes index i available to the next sibling branch.

The undo operations must restore both kinds of state. Removing the value from path but leaving used[i] true blocks valid future branches. Resetting used[i] but forgetting to pop leaves the path with a value that belongs to a different branch.

Backtracking is controlled mutation. Choose. Recurse. Undo. Every step must be reversible.

Complexity, mistakes, and edge cases

Let n = len(nums) and let P be the number of distinct permutations returned.

Sorting costs:

[ O(n \log n) ]

Each completed result requires copying a path of length n, so output construction costs:

[ O(nP) ]

The duplicate-aware search has a safe worst-case time bound of:

[ O(n \cdot n!) ]

This occurs when values are distinct and the search explores the full permutation space. With duplicates, the number of leaves is smaller, although the loop still scans candidate indices at each recursive depth. For example, an all-equal input has only one output but still performs scans through the input at several levels.

Space has two parts:

• O(n) auxiliary working space for path, used, and recursion depth.
• O(nP) space for the returned permutations.

The returned output is usually the dominant cost. You cannot avoid storing it if the contract requires returning every permutation.

Common mistakes

Skipping every repeated value

This is too aggressive:

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

It rejects valid deeper placements such as the second 1 in [1, 1].

The predecessor must be unused for the skip to apply:

not used[i - 1]

Omitting sorting

Without sorting, equal values may not be adjacent. The comparison with nums[i - 1] then cannot reliably identify duplicate choices.

Tracking only values instead of indices

The two 1s are equal in value but still represent two available occurrences. A used array lets the search consume each occurrence exactly once while the duplicate rule controls which equivalent branch starts first.

Appending path directly

This is wrong:

result.append(path)

All stored entries would refer to the same mutable list. Use:

result.append(path.copy())

Failing to undo state

After recursion returns, restore both:

path.pop()
used[i] = False

Backtracking works only when each branch receives a clean version of the state that existed before the branch began.

Edge cases

• One element: the single-element permutation is returned.
• All values equal, such as [2, 2]: exactly one permutation is returned.
• All values distinct, such as [1, 2, 3]: the duplicate condition never fires.
• Mixed frequencies, such as [1, 1, 2, 2]: each equal group is skipped only among siblings, while both copies can still occupy different positions.

The transferable pattern

When a backtracking loop contains equal choices, ask one question:

Are these equal choices interchangeable at this recursion depth?

If yes, sort or group the values and explore one canonical representative for that level. If an equal value has already been used earlier in the current path, allow the next occurrence: it may be filling a different position and creating a genuinely different arrangement.

For this problem, repeat the implementation check out loud:

Skip an equal index only when its previous equal occurrence is unused.

Then test [1, 1, 2] and [2, 2]. If the first produces three outputs and the second produces one, your duplicate backtracking rule is respecting both boundaries: no repeated branches, no lost repeated values.