Permutations

A permutation of a set of n distinct elements is a linear ordering of those elements. There are n! = n · (n-1) · ... · 1 permutations of an n-element set, a count that grows faster than any polynomial and reaches ~3.6 million already at n = 10. The interview canon contains three permutation problems: (1) enumerate all n! permutations of a set (LeetCode 46); (2) enumerate all distinct permutations of a multiset (a list with possible duplicates, LeetCode 47); and (3) find the next permutation in lexicographic order in place (LeetCode 31). Three primary implementation strategies appear: a backtracking schema with a used array (clean and general), an in-place swap variant (no extra memory), and Heap’s algorithm (Heap 1963) which generates each successive permutation with a single swap from its predecessor. The duplicates problem is solved by sorting the input and skipping a value at the same recursion level whenever it equals the previous and the previous wasn’t taken — the same “sort + level-skip” pattern that recurs in Combinations and Subsets.

1. Intuition — Filling Slots One at a Time

To list every permutation of {1, 2, 3}:

• Pick what goes in slot 1. There are 3 choices: 1, 2, or 3.
• Whatever you picked, pick what goes in slot 2 from the remaining 2.
• The slot-3 element is determined.

That gives a tree of decisions: 3 choices at the root × 2 at depth 1 × 1 at depth 2 = 3! = 6 leaves, each a distinct permutation. The “remaining” set shrinks as we descend; tracking which elements are still available is the entire bookkeeping problem. Backtracking represents “remaining” with a used[] boolean array; the in-place swap variant represents it implicitly by partitioning the array into a “fixed prefix” and a “swappable suffix”; Heap’s algorithm exploits a clever recurrence to perform exactly one swap per emitted permutation.

2. Tiny Worked Example — Trace All 6 Permutations of [1, 2, 3]

The state-space tree (with used = [F,F,F] initially):

                          []
        ┌──────────────────┼──────────────────┐
       [1]                [2]                [3]
     ┌───┴───┐          ┌───┴───┐          ┌───┴───┐
   [1,2]   [1,3]      [2,1]   [2,3]      [3,1]   [3,2]
     │       │          │       │          │       │
  [1,2,3] [1,3,2]    [2,1,3] [2,3,1]    [3,1,2] [3,2,1]   ← 6 leaves

Each leaf has length n = 3. The number of leaves is 3! = 6. Internal nodes carry partial permutations; the algorithm visits a leaf, snapshot-copies the current path, returns up the recursion via the undo step, and tries the next sibling.

For the in-place swap variant, the trace is structurally identical but the path field is the array itself; “choose element i for slot s” is swap(arr[s], arr[i]) and undo is swap(arr[i], arr[s]) (the same swap, since swap is self-inverse).

3. Pseudocode — The Backtracking Schema

permute(nums):
    n := length(nums)
    results := []
    path := []
    used := array of n booleans, all false

    define go():
        if length(path) == n:
            append copy(path) to results
            return
        for i := 0 to n - 1:
            if used[i]:
                continue
            push nums[i] onto path
            used[i] := true
            go()                          # recurse
            pop path
            used[i] := false              # undo (mirror image)

    go()
    return results

The five mandatory pieces from Backtracking Framework map directly:

• is_solution(state) ↔ length(path) == n
• choices(state) ↔ for i := 0 to n - 1
• valid(choice, state) ↔ not used[i]
• apply(choice, state) ↔ push + mark used
• undo(choice, state) ↔ pop + unmark (mirror)

4. Python Implementations — Three Variants

4.1 Backtracking with used Array (clearest)

def permutations(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    results: list[list[int]] = []
    path: list[int] = []
    used = [False] * n
 
    def go():
        if len(path) == n:
            results.append(path[:])       # snapshot
            return
        for i in range(n):
            if used[i]:
                continue
            path.append(nums[i]); used[i] = True
            go()
            path.pop();           used[i] = False
 
    go()
    return results

This version is the closest to the canonical Backtracking Framework schema. Both path and used are mutated and undone — the asymmetry of forgetting one undo is the most common bug.

4.2 In-Place Swap (no extra memory)

The trick: keep the array in two regions, a “fixed prefix” and a “swappable suffix”. To pick the next slot’s value, swap any suffix element into the boundary; recurse on the slimmer suffix; swap back.

def permutations_swap(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    results: list[list[int]] = []
    arr = nums[:]                          # don't mutate the caller's list
 
    def go(start: int):
        if start == n:
            results.append(arr[:])
            return
        for i in range(start, n):
            arr[start], arr[i] = arr[i], arr[start]    # apply: bring nums[i] into slot 'start'
            go(start + 1)
            arr[start], arr[i] = arr[i], arr[start]    # undo: same swap, since swap is its own inverse
 
    go(0)
    return results

Memory: O(n) recursion stack, O(n) for the in-place array. No used[] array. The output collection is the dominant cost.

Subtle

The swap variant does not generate permutations in lexicographic order even on a sorted input. The used-array variant does (when iterating i from 0 to n-1 and nums is sorted). If lexicographic order matters, prefer the used variant or post-sort.

4.3 Heap’s Algorithm — One Swap per Permutation

Discovered by B. R. Heap in 1963 (Heap 1963), this is the most efficient sequential generator: each successive permutation is obtained by exactly one swap from its predecessor. Sedgewick’s 1977 survey of permutation algorithms (ACM Computing Surveys 9.2) ranks Heap’s as the fastest in practice for emit-all-permutations.

The recurrence Heap exploits: to generate all permutations of arr[0..n-1],

1. Generate all permutations of arr[0..n-2] (recursive call), which fixes arr[n-1] in the last slot.
2. Then for each i from 0 to n-2, swap arr[i] with arr[n-1] (or with arr[0], depending on n’s parity), and re-generate all permutations of arr[0..n-2].

The “or with arr[0]” parity dance is the cleverness: it’s chosen so that the full arrangement at the end of step 2 is one swap away from the initial arrangement, allowing the algorithm to be expressed as a single sweep without rewinding state.

def permutations_heap(nums: list[int]) -> list[list[int]]:
    arr = nums[:]
    results: list[list[int]] = []
 
    def go(k: int):
        if k == 1:
            results.append(arr[:])
            return
        for i in range(k):
            go(k - 1)
            if k % 2 == 0:
                arr[i], arr[k - 1] = arr[k - 1], arr[i]    # swap arr[i] with last
            else:
                arr[0], arr[k - 1] = arr[k - 1], arr[0]    # swap arr[0] with last
 
    go(len(arr))
    return results

The number of swaps performed is exactly n! − 1, the theoretical minimum (you need at least one swap to move from one permutation to a different one, and you have n! − 1 transitions).

The recursive parity-based formulation above is the one given in the Wikipedia treatment of Heap’s algorithm, which states the rule precisely: “If k is even, then the final element is iteratively exchanged with each element index. If k is odd, the final element is always exchanged with the first.” Robert Sedgewick’s 1977 survey “concluded that it was at that time the most effective algorithm for generating permutations by computer” (per the same article). Verified by direct trace: the go above emits exactly n! distinct permutations on [1,2,3] (and on multisets, the correct count of arrangements). Wikipedia also gives an iterative version that replaces the call stack with an explicit c[] counter array — c[k] records the loop counter for recursion level k; an index i acts as a stack pointer, performing the parity swap and resetting i = 1 on c[i] < i, or resetting c[i] and incrementing i to simulate unwinding. The two versions enumerate in the same order.

Uncertain

Verify: that the parity-based swap rule is verbatim the formulation in Heap’s original 1963 paper (The Computer Journal 6.3: 293–294), as opposed to a later restatement. Reason: the original paper is paywalled and was not retrieved during this write-up; Wikipedia cites it but does not reproduce its exact swap rule, and several distinct-but-equivalent bookkeeping variants of “Heap’s algorithm” circulate. To resolve: read the 1963 paper directly. This is a historical-fidelity question only — the algorithm’s correctness (it generates all n! permutations in n! − 1 swaps) is verified above by trace and is not in doubt. uncertain

4.4 Permutations with Duplicates (LeetCode 47)

When nums may contain duplicates and we want each distinct permutation once, the trick is sort the input + skip a value at the same recursion level whenever it equals the previous and the previous is not currently used.

def permutations_unique(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)                    # 1) sort
    n = len(nums)
    results, path = [], []
    used = [False] * n
 
    def go():
        if len(path) == n:
            results.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            # 2) skip duplicate at same level
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            path.append(nums[i]); used[i] = True
            go()
            path.pop();           used[i] = False
 
    go()
    return results

Why not used[i - 1] and not used[i - 1]? This is the most error-prone line in all of backtracking. The intent of the skip is: among a run of equal values nums[i-1] = nums[i] = ..., fix a canonical order in which we use them. The canonical order chosen is “left to right”: within a group of equals, we may use the i-th occurrence only after we’ve used the (i-1)-th in the same root-to-leaf path. So when we are about to use nums[i] and find nums[i-1] == nums[i], we skip iff nums[i-1] was not yet used (meaning we’d be picking the duplicate in the wrong order, which would generate a duplicate permutation later).

The used[i-1] = True case means we’ve already committed nums[i-1] earlier in the current path — picking nums[i] next is the canonical extension and must not be skipped.

Working through it on [1, 1, 2]:

• root, i = 0: nums[0] = 1, no previous → use. path = [1], used = [T,F,F].
  • i = 0: skip (used).
  • i = 1: nums[1] = 1, nums[0] = 1, used[0] = T → don’t skip. path = [1,1]. → Eventually [1,1,2].
  • i = 2: nums[2] = 2, no skip. path = [1,2]. → [1,2,1].
• root, i = 1: nums[1] = 1, nums[0] = 1, used[0] = F → skip. (This is the duplicate-prevention.)
• root, i = 2: nums[2] = 2. Use. → eventually [2,1,1].

Result: 3 distinct permutations [1,1,2], [1,2,1], [2,1,1]. Without the skip we’d produce 6 with two pairs of duplicates.

The exact same predicate (sort + level-skip with the used[i-1] analogue) recurs in Combinations (LC 40) and Subsets (LC 90), where the “level” is encoded by a start index instead of a used array — the predicate becomes if i > start and nums[i] == nums[i-1]: continue. The mathematical content is the same: pick a canonical ordering among ties to suppress the duplicates.

5. Complexity

5.1 Counting Operations

The recursion visits n! leaves; the path snapshot at each leaf is O(n) work. The total time is O(n · n!).

The space is dominated by the output (each of n! results is a length-n list = O(n · n!) total). Excluding the output, the algorithm uses O(n) recursion stack + O(n) for path and used = O(n) auxiliary.

For n = 10: n! ≈ 3.6 × 10⁶, n · n! ≈ 3.6 × 10⁷ — fast enough. For n = 12: n! ≈ 4.8 × 10⁸, n · n! ≈ 5.7 × 10⁹ — too slow. Backtracking permutation enumeration is bounded by n ≤ 10 or so in practice. Beyond that, you typically need lazy generation (yield rather than store) or a different problem formulation (e.g., random sampling).

5.2 Why It’s Asymptotically Optimal

You cannot enumerate n! outputs in better than Ω(n!) time, since you must produce that many results. Each result has length n, so the output size alone is Θ(n · n!). The algorithms above match this bound, so they are asymptotically optimal up to constant factors. Heap’s algorithm has the smallest constant (one swap per emit) but the same O(n · n!) total because emitting still requires a length-n snapshot.

5.3 Recursion Depth

Recursion depth is exactly n. Python’s default limit (1000) handles n up to ~990 in principle — but n = 990! is astronomically larger than the universe’s particle count, so depth is irrelevant in practice; runtime hits its asymptote first.

6. Next Permutation in Lexicographic Order (LeetCode 31)

A separate but related problem: given an array, mutate it in place to the next permutation in lexicographic order. If the array is already the last (descending) permutation, wrap around to the first (ascending).

The algorithm (Knuth, The Art of Computer Programming Vol. 4A §7.2.1.2, “Algorithm L”) is O(n) and elegant:

next_permutation(arr):
    # 1. find the largest i such that arr[i] < arr[i+1]
    i := length(arr) - 2
    while i >= 0 and arr[i] >= arr[i+1]:
        i := i - 1
    if i >= 0:
        # 2. find the largest j such that arr[j] > arr[i]
        j := length(arr) - 1
        while arr[j] <= arr[i]:
            j := j - 1
        # 3. swap arr[i] and arr[j]
        swap(arr[i], arr[j])
    # 4. reverse arr[i+1 .. end]
    reverse(arr[i+1 ..])

def next_permutation(arr: list[int]) -> None:
    n = len(arr)
    # 1) find pivot
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i >= 0:
        # 2) find rightmost successor to pivot
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        # 3) swap
        arr[i], arr[j] = arr[j], arr[i]
    # 4) reverse the suffix
    arr[i + 1:] = reversed(arr[i + 1:])

Why it works. A permutation written left-to-right has a unique structure: the suffix arr[i+1..] is in descending order iff arr[i] ≥ arr[i+1] and there’s no further increasing pair to the right. Step 1 finds the rightmost i not in such a maximal-descending suffix — arr[i] is the pivot, the digit we’ll bump up. Step 2 finds the smallest element in the suffix still bigger than the pivot — call it arr[j]. Step 3 swaps; now arr[0..i] is one notch up from before. Step 4 reverses the suffix, putting it in ascending order — the smallest possible continuation, so the result is the immediate successor.

For sorted input [1, 2, 3]:

• Step 1: i = 1 (since arr[1] = 2 < 3 = arr[2]).
• Step 2: j = 2 (arr[2] = 3 > 2).
• Step 3: swap → [1, 3, 2].
• Step 4: reverse arr[2..] (single element) → [1, 3, 2].

That’s the lex-next permutation of [1, 2, 3]. ✓ Doing this n! − 1 times generates every permutation in lex order, with O(n) work per step — a different O(n · n!) algorithm than the backtracking one, but in streaming fashion (one permutation at a time, no recursion).

7. Generation Order Comparison

Algorithm	Output order	Work per permutation	Auxiliary memory
Backtracking with used[]	Lexicographic (if nums is sorted)	O(n) (snapshot copy)	O(n)
In-place swap	Not lex; “swap order”	O(n) (snapshot)	O(n) array
Heap’s algorithm	Heap-specific (not lex)	O(n) snapshot, but 1 swap vs many	O(n) recursion stack
Iterated next-permutation	Lexicographic	O(n) swap+reverse	O(1) auxiliary
All-at-once itertools.permutations (Python)	Lexicographic	O(n) per yield	O(n)

If you only need one random permutation, the Fisher–Yates shuffle gives a uniform random permutation in O(n):

import random
def shuffle(arr):
    for i in range(len(arr) - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]

This is what Python’s random.shuffle actually does. It’s not “permutation generation” in the enumeration sense, but it answers a related interview question.

8. Diagram — The Permutation State-Space Tree for n = 3

flowchart TD
    R["[]<br/>used=[F,F,F]"]
    R --> A1["[1]<br/>used=[T,F,F]"]
    R --> A2["[2]<br/>used=[F,T,F]"]
    R --> A3["[3]<br/>used=[F,F,T]"]
    A1 --> B1["[1,2]"]
    A1 --> B2["[1,3]"]
    A2 --> B3["[2,1]"]
    A2 --> B4["[2,3]"]
    A3 --> B5["[3,1]"]
    A3 --> B6["[3,2]"]
    B1 --> L1["[1,2,3]"]
    B2 --> L2["[1,3,2]"]
    B3 --> L3["[2,1,3]"]
    B4 --> L4["[2,3,1]"]
    B5 --> L5["[3,1,2]"]
    B6 --> L6["[3,2,1]"]

What this diagram shows. The state-space tree of the used-array backtracker on [1, 2, 3]. At depth 0 the partial path is empty. At depth d the partial has length d, and the next level has n − d children (only the unused indices). The 6 leaves at depth 3 are the 6 permutations, emitted left-to-right in lexicographic order. Each non-leaf edge is an apply/undo pair on path and used. With duplicates (e.g., input [1, 1, 2]), the level-skip prune cuts off some children at the second step, leaving 3 leaves instead of 6.

9. Pitfalls

1. results.append(path) instead of results.append(path[:]). Every recorded result aliases the same path, which is empty by the end of the traversal. Always snapshot. (See Backtracking Framework §10.3.)
2. Forgetting to undo used[i]. Path is rewound by the natural pop() but the boolean stays set, blocking future branches from using the value. The most common single bug.
3. Wrong duplicate-skip predicate. if i > 0 and nums[i] == nums[i-1] and not used[i-1] — the not used[i-1] is the part everyone gets backwards. The not is correct: skip iff the previous duplicate was NOT used in the current path. (Fully derived in §4.4.)
4. Forgetting to sort before deduplication. The level-skip predicate relies on equal values being adjacent. [1, 2, 1] without sorting won’t deduplicate correctly.
5. Generating permutations with repetition by accident. If you forget the used[i] check entirely, you generate n^n “tuples” (Cartesian product), not n! permutations.
6. Mutating the caller’s input. The in-place swap variant mutates arr. If the caller hands in a list they expect unchanged, copy first (arr = nums[:]).
7. Recursion depth on extreme inputs. Not really a problem for permutations (n! blows up the time well before n blows up the depth), but mentioning for parity with Subsets which can have n ≈ 1000+.
8. Mutable default argument. def go(path=[]): ... — Python evaluates [] once at definition time, sharing across calls. Use path=None and path = [] if path is None else path. This isn’t backtracking-specific, but it intersects with backtracking’s heavy reliance on shared mutable state.
9. Confusing permutations with combinations. Permutations care about order; combinations don’t. [1, 2] and [2, 1] are the same combination but different permutations. If the interview problem asks for “all subsets of size k” or “all k-tuples without order”, reach for Combinations, not this note.
10. Thinking Heap’s algorithm produces lex order. It produces a specific sequence with one swap between consecutive permutations, but that sequence is not lex order. Don’t quote it for problems that require lex output.
11. Returning from the leaf without first emitting. The leaf condition len(path) == n should snapshot then return. A common refactor accidentally inverts the order and produces no output.

10. Common Interview Problems

Problem	LeetCode	Difficulty	Variation
Permutations	46	Medium	Distinct elements
Permutations II	47	Medium	Duplicates; sort + level-skip
Next Permutation	31	Medium	In-place lex successor
Permutation Sequence	60	Hard	Find the k-th permutation directly via factorial decomposition
Letter Case Permutation	784	Medium	Permute character cases (subset variant)
Permutation in String	567	Medium	Sliding-window check using char counts
Find All Anagrams in a String	438	Medium	Cousin of 567
Beautiful Arrangement	526	Medium	Permutation with positional divisibility constraint — backtracking + pruning

11. Open Questions

• When does the in-place swap variant differ from the used[] variant in practice beyond order? They visit the same number of nodes; constant factors are similar. The swap variant saves the used[] allocation.
• Sedgewick (1977) classifies permutation-generation algorithms into a taxonomy of ~10 methods. Are any other than backtracking/Heap’s commonly tested in interviews? (Anecdotally: no — those two cover everything.)
• The n = 12 cliff: are there problem variants where you really need to enumerate n = 15+ permutations? Usually that’s a sign the problem reduces to dynamic programming over states (Bitmask DP) or has special structure.

12. See Also

• Backtracking Framework — the meta-skeleton; this note is one of four canonical instantiations
• Combinations, Subsets — siblings using the same level-skip duplicate trick
• Bitmask DP — when permutation states fit in a bitmask, often the right tool for n ≤ 20 ordering problems
• Depth-First Search — backtracking is DFS over the state-space tree
• N-Queens — a constrained permutation (each queen’s column is a permutation of 0..n-1, restricted by diagonals)
• Recursion vs Iteration — the iterated next-permutation is the iterative analogue
• Big-O Notation — for the O(n · n!) analysis
• SWE Interview Preparation MOC