cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 95 of 218
Ideas this builds on
Backtracking95 / 218

Permutations with duplicates

Picture

Permuting [1,1,2] by item position generates duplicate value sequences when the two 1s swap identities.

Predict

Should every repeated value be skipped globally?

Walk through the small example

No. Sorting makes equal sibling choices adjacent, and a depth-local rule removes symmetric branches.

Mental model and complete Python solution

Duplicates are not forbidden items; they are indistinguishable choices. Skip only the second twin when the first twin was available at this same branch point.

What the function promises: Return all distinct list permutations in lexicographic order.

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

assert unique_permutations([1,1,2]) == [[1,1,2],[1,2,1],[2,1,1]]
assert unique_permutations([]) == [[]]

Work and storage: O(U·n) output work for U distinct permutations, plus O(n) active state.

When to recognize it: Sorting makes equal sibling choices adjacent, and a depth-local rule removes symmetric branches.

Check before applying it: Using a global value set loses required repeated copies; output size can still be enormous.

Change one rule

Return only the count.

See what changes

Use factorial counts divided by duplicate factorials instead of enumerating outputs.

Connect

backtracking: The prefix is built by choose, recurse, and undo.

Sorting: buy useful order: Sorting makes equivalent sibling choices detectable.