Permutations

Permutations are selections where order matters: [1, 2] and [2, 1] are different answers. Subsets and combinations only look forward from a start index. Here every position may take any element not used yet. The tree has N choices at the first level, N − 1 at the next, and so on, which gives N! leaves.

The idea#

Build the answer one position at a time:

1. Choices: every element not already in the path, so the loop always runs over all n indices with a used check.
2. State: the path so far and a used array (or set).
3. Goal: the path has n elements; snapshot a copy.

Why it works: each level fixes one position, and the used check guarantees every element appears exactly once. Every ordering is one root-to-leaf path, so none is missed and none repeats (when the values are distinct).

The cost follows from the size of that tree. There are $N!$ leaves and each copy costs $O(N)$, so time is $O(N \cdot N!)$. The recursion is N deep and the used array is size N, so the extra space is $O(N)$, not counting the output.

Slicing vs a used array#

You need some way to track which elements are still free, and the choice affects memory. A tempting version passes the remaining elements down by slicing: find(path + [x], rest[:i] + rest[i + 1:]). It's correct, but each level makes new lists, and all N frames are alive at once: N + (N − 1) + … + 1 = $O(N^2)$ extra memory. The used array with append and pop keeps it at $O(N)$.

Duplicate values#

When the input has repeated values, two equal elements produce the same orderings twice. The fix is to sort first, so equal values sit next to each other, and then force equal values into a fixed order. Working out the exact skip condition is part of Permutations II.

How to spot it#

These cues point to permutations.

• "All permutations", "all arrangements", "all orderings".
• Each position must take a different element.
• Constraints such as N ≤ 8 to 12, where N! is still affordable.
• A permutation with rules about where each element may go (divisibility, adjacency, attacking queens).

Template#

The template fills one position per call by trying every unused element there. It also has a slot for placement rules, explained right after it.

track():
    if length of path == n:
        record a copy of path
        return
    for i from 0 to n - 1:             # every position sees every element
        if used[i]: continue
        if placing items[i] here breaks a rule: continue   # prune early
        mark i used; append items[i] to path
        track()
        pop from path; unmark i
track()

Check placement rules in the loop, before you place the value, not at the leaf. A bad prefix is then cut immediately instead of being completed in every way and then rejected.

Pitfalls#

Watch for these when moving from combinations to permutations.

• Looping from start. That generates combinations, not permutations; permutations always loop from 0.
• Forgetting to reset used[i] after the recursive call.
• Deduplicating with path not in res. It works, but each check scans every result so far. Sort and skip siblings instead.
• Under-counting memory with slicing. It's $O(N^2)$ auxiliary, not $O(N)$.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Permutations.

• 46. Permutations
• 47. Permutations II
• 526. Beautiful Arrangement
• 51. N-Queens

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Order matters, so every position loops over all elements, filtered by used.
• Time is $O(N \cdot N!)$; extra space is $O(N)$ with a used array, $O(N^2)$ with slicing.
• Duplicates: sort, then force equal values into a fixed order.
• Check placement rules before recursing, not at the leaf.