Permutations

Permutations differ from subsets in one way that changes the whole template: order matters. [1, 2, 3] and [3, 2, 1] are different answers. So the "only look to the right" start index from Subsets no longer works — every element must be a candidate for every position.

That one change swaps the start index for a used array, moves the "record" line to the leaves, and doubles the undo work.

The problem

Given a list of distinct integers, return every possible ordering of them. Any order of the output is fine.

• [1, 2, 3] → [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]. Three choices for the first slot, two for the second, one for the last: 3! = 6.
• [5] → [[5]].

Constraints: 1 ≤ n ≤ 6, values between −10 and 10, all distinct.

Clarifying questions

• Distinct values? Yes for now. Repeats are the follow-up at the end.
• Any output order? Yes.
• Return new lists, or may I change the input? Return new lists; the swap version will change a copy.
• n = 0? Not in the constraints, but the natural answer is [[]] — one empty ordering.

Approach 1: the simple way — build every sequence, then filter

Fill n slots, and let each slot take any index from 0 to n − 1. That gives nⁿ sequences. Keep only those where no index repeats.

1import itertools23def permutations_brute(nums: list[int]) -> list[list[int]]:4    """Every length-n sequence of indices, keeping those with no repeat."""5    n = len(nums)6    return [[nums[i] for i in idx]7            for idx in itertools.product(range(n), repeat=n)8            if len(set(idx)) == n]

Complexity: nⁿ sequences, each checked in O(n): O(n × nⁿ).

Why it is too slow. It builds a sequence first and checks it after. For n = 6 it builds 46,656 sequences to keep 720. For n = 8 it builds 16,777,216 to keep 40,320 — over 400 wasted for every good one. The sequence [0, 0, ...] is already dead after two slots, but this code keeps filling it.

The key insight

Check while building, not after. When you fill a slot, only offer the indices not yet placed. Then every sequence you complete is already a valid ordering, and there is no waste at all: the tree has exactly n! leaves.

To know which indices are placed, keep a boolean array used. It does the job the start index did in Subsets: it controls which choices are legal at each node. The difference is that the start index says "only to the right", while used says "anything not yet taken, left or right". That is exactly what "order matters" needs.

Approach 2: the used array

1def permutations(nums: list[int]) -> list[list[int]]:2    """Every ordering of distinct nums, using a used[] array."""3    result: list[list[int]] = []4    path: list[int] = []5    used = [False] * len(nums)67    def backtrack() -> None:8        if len(path) == len(nums):          # a full ordering9            result.append(path[:])10            return11        for i in range(len(nums)):          # every index is a candidate12            if used[i]:13                continue                    # already placed in this ordering14            used[i] = True15            path.append(nums[i])16            backtrack()17            path.pop()                      # two things chosen...18            used[i] = False                 # ...two things undone1920    backtrack()21    return result

Step by step:

1. Finish rule — the path holds all n numbers. Only leaves are answers, so record and return.
2. Loop from 0 — every index, every time, because any unplaced number can go in the next slot.
3. Skip placed indices — used[i] is the prune. It removes nⁿ − n! dead sequences before they start.
4. Two changes, two undos — used[i] and path both change on the way down, so both are restored on the way up.

Dry run on [1, 2, 3], the first two orderings:

From step 8 the same walk runs with 2 first, then with 3 first. The output order is [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] — the order the code really produces.

Complexity. There are n! leaves and each copy costs O(n), so O(n × n!) time. Counting the inner nodes too, the tree has n!/0! + n!/1! + n!/2! + … nodes, which is under e × n!, so the bound holds. Working space is O(n) for path, used and the stack; the output is O(n × n!).

Approach 3: swap in place

You can drop both path and used. Keep the array itself split in two: positions before first are fixed, positions from first on are the numbers still free. To fill position first, swap each free number into it in turn.

1def permutations_swap(nums: list[int]) -> list[list[int]]:2    """Every ordering, built in place by swapping."""3    arr = nums[:]                                      # don't change the caller's list4    result: list[list[int]] = []56    def backtrack(first: int) -> None:7        if first == len(arr):8            result.append(arr[:])9            return10        for i in range(first, len(arr)):11            arr[first], arr[i] = arr[i], arr[first]    # choose arr[i] for this slot12            backtrack(first + 1)13            arr[first], arr[i] = arr[i], arr[first]    # undo: swap back1415    backtrack(0)16    return result

Same O(n × n!) time, less extra memory, and the choose and undo are the same swap. The catch: the output order differs ([3, 2, 1] comes before [3, 1, 2]), and the duplicate rule below is harder to add, so the used version is the safer default.

When the input has repeats (Permutations II)

With [1, 1, 2] the template builds 6 orderings but only 3 are different: [1, 1, 2], [1, 2, 1], [2, 1, 1]. Swapping the two 1s makes no visible change.

The fix, as in Subsets: sort, then make equal values be used left to right. The second 1 may be placed only if the first 1 is already in the path.

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:    continue          # the equal value to my left is free: it must go first

Add that line after the used[i] check (and sort nums first). Read the last clause carefully. not used[i - 1] means the equal value to the left is not in the path right now. Placing this copy first would create an ordering that the branch using the left copy already covers. If used[i - 1] is True, the left copy is placed and this one is a genuine second 1.

On [1, 1, 2]: at the root, i = 1 is skipped because nums[1] == nums[0] and used[0] is False. Inside the i = 0 branch, used[0] is True, so i = 1 is allowed and [1, 1, 2] is built. Three results, none repeated.

Edge cases

• One element — one ordering, [[5]].
• Negative values — no effect; values are never compared in the distinct version.
• All equal with repeats allowed — [2, 2, 2] must give exactly one ordering. The not used[i - 1] rule allows only the left-to-right order.
• Changing the input — the swap version works on a copy so the caller's list is untouched.

Follow-ups

• Next permutation — no backtracking: from the right, find the first drop, swap it with the smallest larger value to its right, then reverse the tail. O(n).
• The k-th permutation — do not list them. With n numbers, each first choice covers (n − 1)! orderings, so divide k by (n − 1)! to pick the first number, then repeat. O(n²).
• Letter case permutations ("a1b" → a1b, a1B, A1b, A1B) — this is Subsets in disguise: each letter is a two-way choice, so there are 2^(letters) answers.