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.

Source

Stanford CS106B: Backtracking

Cost​

Source​

Cost

Source