Permutations by Backtracking

At depth $k$, choose which unused input position supplies output position $k$. Tracking positions—not only values—preserves correct multiplicity.

def unique_permutations(values: list[int]) -> list[list[int]]:
    values = sorted(values)
    used = [False] * len(values)
    path: list[int] = []
    result: list[list[int]] = []

    def visit() -> None:
        if len(path) == len(values):
            result.append(path.copy())
            return
        for i, value in enumerate(values):
            if used[i]:
                continue
            if i > 0 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 result

Sorting groups equal values. At one decision level, the duplicate rule permits only the first currently unused copy, removing symmetric branches without removing any distinct permutation.

Cost

For $n$ distinct values there are $n!$ outputs, each of length $n$, so materializing all results requires $\Theta(n\cdot n!)$ output work and space. Backtracking adds $O(n)$ path, used-state, and recursion space beyond the output.

When results are consumed incrementally, a generator avoids storing the full output but cannot avoid the output-size time lower bound.

Duplicate trace and the empty permutation

For [1,1,2], the root may choose the first 1 or the 2, but skips the second 1. After choosing the first 1, the second 1 becomes eligible: using it gives [1,1,2], while choosing 2 next gives [1,2,1]. The root branch beginning with 2 gives [2,1,1]. This retains both copies where needed while eliminating only their interchangeable identities.

The path length increases on every recursive call and is bounded by n, so recursion terminates. Empty input returns [[]], not []: there is one permutation of zero elements. For multiplicities m₁,…,mᵣ the number of distinct outputs is n!/(m₁!…mᵣ!). This code still scans n positions at each internal node, so do not infer that its runtime is always proportional only to the number of distinct outputs. If all values are equal, there is one output but Θ(n²) scanning work.

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

Source

• Stanford CS106B: Backtracking

My reading · Opened notes are remembered in this browser.