155. Generate Unique Permutations

Why this mechanism works

The used-index protocol still works, but identical unused values at the same decision level create identical subtrees. Require equal occurrences to be selected from left to right: skip an occurrence if its equal predecessor is currently unused. If that predecessor is already on the path, the next equal occurrence remains a valid choice.

State and boundaries

values is sorted. used marks selected occurrences. A branch chooses the first currently unused occurrence of any equal value.

Protocol

1. Sort a copy.
2. At each depth scan unused indices.
3. Skip an equal value whose previous occurrence is unused.
4. Choose, explore and undo.
5. Copy complete paths.

Visualization

sorted [1a,1b,2]
root may choose 1a; skip 1b while 1a is unused
after choosing 1a, choosing 1b is allowed

Python implementation

def unique_permutations(nums):
    values = sorted(nums)
    used = [False] * len(values)
    output, path = [], []
    def visit():
        if len(path) == len(values):
            output.append(path.copy())
            return
        for i, value in enumerate(values):
            if used[i]:
                continue
            if i and value == values[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(value)
            visit()
            path.pop()
            used[i] = False
    visit()
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 unique_permutations: values = sorted(nums)
nums=[1, 1, 2]; values=[1, 1, 2]

L3 unique_permutations: used = [False] * len(values)
nums=[1, 1, 2]; values=[1, 1, 2]; used=[False, False, False]

L4 unique_permutations: output, path = [], []
nums=[1, 1, 2]; values=[1, 1, 2]; used=[False, False, False]; output=[]; path=[]

L6 visit: if len(path) == len(values):
output=[]; path=[]; used=[False, False, False]; values=[1, 1, 2]

L9 visit: for i, value in enumerate(values):
output=[]; path=[]; used=[False, False, False]; values=[1, 1, 2]; i=0; value=1

L14 visit: used[i] = True
output=[]; path=[]; used=[True, False, False]; values=[1, 1, 2]; i=0; value=1

L15 visit: path.append(value)
output=[]; path=[1]; used=[True, False, False]; values=[1, 1, 2]; i=0; value=1

L6 visit: if len(path) == len(values):
output=[]; path=[1]; used=[True, False, False]; values=[1, 1, 2]

... 62 intermediate state changes omitted ...

L16 visit: visit()
output=[[1, 1, 2], [1, 2, 1], [2, 1, 1]]; path=[2]; used=[False, False, True]; values=[1, 1, 2]; i=2; value=2

L17 visit: path.pop()
output=[[1, 1, 2], [1, 2, 1], [2, 1, 1]]; path=[]; used=[False, False, True]; values=[1, 1, 2]; i=2; value=2

L18 visit: used[i] = False
output=[[1, 1, 2], [1, 2, 1], [2, 1, 1]]; path=[]; used=[False, False, False]; values=[1, 1, 2]; i=2; value=2

L19 unique_permutations: visit()
nums=[1, 1, 2]; values=[1, 1, 2]; used=[False, False, False]; output=[[1, 1, 2], [1, 2, 1], [2, 1, 1]]; path=[]

L2 unique_permutations: values = sorted(nums)
nums=[2, 2]; values=[2, 2]

L3 unique_permutations: used = [False] * len(values)
nums=[2, 2]; values=[2, 2]; used=[False, False]

L4 unique_permutations: output, path = [], []
nums=[2, 2]; values=[2, 2]; used=[False, False]; output=[]; path=[]

L6 visit: if len(path) == len(values):
output=[]; path=[]; used=[False, False]; values=[2, 2]

L9 visit: for i, value in enumerate(values):
output=[]; path=[]; used=[False, False]; values=[2, 2]; i=0; value=2

L14 visit: used[i] = True
output=[]; path=[]; used=[True, False]; values=[2, 2]; i=0; value=2

L15 visit: path.append(value)
output=[]; path=[2]; used=[True, False]; values=[2, 2]; i=0; value=2

L6 visit: if len(path) == len(values):
output=[]; path=[2]; used=[True, False]; values=[2, 2]

... 10 intermediate state changes omitted ...

L17 visit: path.pop()
output=[[2, 2]]; path=[]; used=[True, False]; values=[2, 2]; i=0; value=2

L18 visit: used[i] = False
output=[[2, 2]]; path=[]; used=[False, False]; values=[2, 2]; i=0; value=2

L9 visit: for i, value in enumerate(values):
output=[[2, 2]]; path=[]; used=[False, False]; values=[2, 2]; i=1; value=2

L19 unique_permutations: visit()
nums=[2, 2]; values=[2, 2]; used=[False, False]; output=[[2, 2]]; path=[]

Why the solution is correct

Every distinct value sequence has one canonical occurrence assignment: equal occurrences are used in increasing index order. The skip rule enforces precisely that assignment without preventing repeated equal values at later depths. Consequently every distinct permutation is generated exactly once in sorted choice order.

Time and space

O(n log n + n*n!) worst-case time, O(n) auxiliary state, and O(n*P) output for P distinct permutations. Duplicate pruning often greatly reduces work.

Common mistakes

Skipping every repeated value would forbid valid answers such as [1,1,2]. Checking whether the previous equal occurrence is used, with the wrong polarity, changes the canonical-choice rule.

Reasoning card

Transfer exercise

Replace used flags with a value-to-remaining-count dictionary. Compare the branching state for duplicate-heavy inputs.