Permutations and Arrangements

Subsets and combinations use a start index, because order does not matter — once you have passed an element you never look back. Permutations are different: every element is available at every depth, just not twice on the same path.

That one change drives everything on this page:

Combinations advance a start pointer. Permutations track which elements are already in use.

The second half of the page is a different problem entirely: computing the next permutation in lexicographic order, in place, without generating any of the others. That algorithm is short, non-obvious, and asked constantly.

What you’ll learn

• The used array template, and why a start index cannot work here.
• The duplicate-skip rule for permutations of a multiset — and why it looks wrong at first glance.
• Why $n!$ output means you cannot beat exponential time, and what that implies.
• Next permutation: the pivot-swap-reverse algorithm in $O(n)$ and $O(1)$ space.
• Three real LeetCode problems solved in the browser: 46, 47, 31.

The cue

You are looking at a permutation problem when…

• “All possible orderings / arrangements / permutations” — 46, 47.
• Order matters and every element must be used — as opposed to subsets, where order does not matter and elements may be skipped.
• “Next” or “previous” permutation in lexicographic order — 31, and its generalisation 556.
• The k-th permutation directly, without enumerating — 60, which is factorial number-system arithmetic rather than backtracking.
• Constraints are tiny (n <= 8 or so). That is a strong signal that factorial output is expected and acceptable.

Visual intuition

The swap-based version, which avoids copying a list per branch. Watch the array get restored on every return:

recursionFix one position at a time — the branching factor shrinks by one per levelLC 46 · n! leaves

call stack

123

1def permutations(nums):2    out = []3    def go(start):4        if start == len(nums):5            out.append(nums[:])6            return7        for i in range(start, len(nums)):8            nums[start], nums[i] = nums[i], nums[start]9            go(start + 1)10            nums[start], nums[i] = nums[i], nums[start]   # swap back11    go(0)12    return out

start0array1,2,3

callFix position 0 first: each of the 3 elements gets a turn there, and each choice spawns a subtree over the remaining positions.

Play‹›1/39⟲

The swap-back on the way out is what lets a single shared array serve the whole tree. Building a fresh list per branch also works and is easier to reason about, but costs O(n · n!) space instead of O(n).

The template

permutations.py

def permute(nums):
    out, path = [], []
    used = [False] * len(nums)
 
    def backtrack():
        if len(path) == len(nums):
            out.append(list(path))          # COPY -- path keeps mutating
            return
        for i in range(len(nums)):          # every index, every time
            if used[i]:
                continue
            used[i] = True                  # choose
            path.append(nums[i])
            backtrack()                     # explore
            path.pop()                      # un-choose
            used[i] = False
 
    backtrack()
    return out
 
 
print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

The loop starts at 0 every time — that is the difference from combinations. The used array is what prevents reusing an element already on the current path.

The two disciplines from backtracking still apply

Copy on record. out.append(list(path)), never out.append(path). path is one list mutated throughout; storing it stores an alias that later pop() calls will empty.

Every choose needs its matching un-choose. Here that means three paired lines: used[i] = True / used[i] = False and path.append / path.pop. Forgetting to reset used[i] silently produces far fewer permutations, because elements stay marked as consumed on sibling branches.

An alternative worth knowing is the swap-based version, which permutes the array in place and needs no used array:

permute_swap.py

def permute_swap(nums):
    out = []
 
    def backtrack(start):
        if start == len(nums):
            out.append(list(nums))
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]   # choose
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]   # un-choose
    backtrack(0)
    return out

It uses less memory, but produces permutations in a different (non-lexicographic) order, and it does not extend cleanly to the duplicate case — which is why the used template is the one to default to.

Handling duplicates

For [1, 1, 2] the plain template produces [1,1,2] twice, because the two 1s are distinct positions even though they are equal values. Sorting first, then skipping, fixes it:

permutations_ii.py

def permute_unique(nums):
    nums.sort()                              # sorting groups equal values
    out, path = [], []
    used = [False] * len(nums)
 
    def backtrack():
        if len(path) == len(nums):
            out.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # skip this duplicate unless its identical predecessor is in use
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False
 
    backtrack()
    return out

Why not used[i - 1] and not used[i - 1]

This condition reads backwards to most people, so it is worth deriving.

Among a run of equal values, we want to fix a single canonical order in which they may be consumed: left to right. So nums[i] may only be used if its identical left neighbour has already been used on this path.

• If used[i-1] is True, the predecessor is on the current path, so we are extending the run in canonical order — allowed.
• If used[i-1] is False, the predecessor is not in use, meaning we would be picking the second copy before the first — a permutation we will generate (or have generated) via the other branch. Skip it.

A caveat, because it is easy to over-claim here: flipping the condition to used[i - 1] is also correct. It simply picks the opposite convention — equal values must be consumed right-to-left instead of left-to-right — and one canonical order is as good as another. Checked against itertools.permutations on [1,1,2], [1,1,1], [1,2,2,2], [1,1,2,3] and [3,3,3,1,1], both versions emit exactly the distinct arrangements, no duplicates and none missing.

What is not optional is the and nums[i] == nums[i-1] guard and the sort. Drop the sort and equal values are no longer adjacent, so the comparison never fires: [1,2,1] emits six results with [1,1,2], [1,2,1] and [2,1,1] each appearing twice. The rule you memorise should be “fix one consumption order within each run of equal values”, not a particular spelling of the boolean.

Dry run

LC 47 — permute_unique([1, 1, 2]), which is the only trace worth walking here because the plain template is unsurprising and the duplicate rule is not. After sorting, nums = [1, 1, 2]; call the two ones 1ₐ (index 0) and 1♭ (index 1).

depth	index	action	path	why
0	0	take 1ₐ	[1]	first copy of the run — always allowed
1	1	take 1♭	[1,1]	used[0] is True, so the run continues in canonical order
2	2	take 2	[1,1,2]	emit [1,1,2]
1	2	take 2	[1,2]	back at depth 1, try the other branch
2	1	take 1♭	[1,2,1]	emit [1,2,1]
0	1	skip 1♭	[]	nums[1] == nums[0] and used[0] is False — starting a path with the second one would duplicate the branch we just finished
0	2	take 2	[2]
1	0	take 1ₐ	[2,1]
2	1	take 1♭	[2,1,1]	emit [2,1,1]
1	1	skip 1♭	[2]	same rule, one level down: 1ₐ is not in use here

Three permutations, not six. What the trace shows that the condition does not:

• The two skips are the entire mechanism, and both happen at the start of a run, never in the middle. 1♭ is skipped exactly when 1ₐ is unused, which means “the first copy is still available, so this branch is a relabelling of one we already explored”.
• [1,1,2] at depth 1 was allowed even though it also uses two equal values — because there used[0] was True. The rule does not forbid repeated values; it forbids consuming them out of order. That distinction is why the condition reads backwards on first sight.
• Without sorting, neither skip fires. For the input [1, 2, 1] the equal values are not adjacent, nums[i] == nums[i-1] is never true, and the output contains [1,1,2] twice. The sort is load-bearing, not tidying.
• Inverting the condition to used[i-1] is equally correct — it fixes the opposite consumption order within each run, and on this input the two skips simply land on different branches. What breaks is dropping the sort: for [1, 2, 1] the equal values are not adjacent, no skip ever fires, and every distinct arrangement is emitted twice.

Complexity, and what it implies

	Time	Space
All permutations (46)	$O(n \cdot n!)$	$O(n)$ recursion, $O(n \cdot n!)$ output
Unique permutations (47)	$O(n \cdot n!)$ worst case, far less with duplicates	$O(n)$
Next permutation (31)	$O(n)$	$O(1)$
k-th permutation (60)	$O(n^2)$	$O(n)$

There are $n!$ permutations and each takes $O(n)$ to write down, so $O(n \cdot n!)$ is optimal — you cannot beat the size of the output. That is why LC 46’s constraint is n <= 6: the problem is not asking you to be clever about complexity, it is asking whether you can enumerate correctly.

Which makes LC 31 the interesting one: it produces one permutation in $O(n)$ without touching the other $n! - 1$.

Next permutation — pivot, swap, reverse

Three steps, and each has a reason:

next_permutation.py

def next_permutation(nums):
    # 1. find the rightmost position that can be increased
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
 
    # 2. swap it with the smallest value to its right that still exceeds it
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
 
    # 3. the suffix was descending (maximal); reverse it to make it minimal
    nums[i + 1:] = reversed(nums[i + 1:])
    return nums

Why this produces exactly the next permutation

After step 1, the suffix nums[i+1:] is non-increasing — it is already the largest arrangement of those values, so nothing there can be increased. That is what makes i the rightmost position where an increase is possible.

Step 2 puts the smallest available value that is still strictly greater than nums[i] into position i. Scanning from the right and stopping at the first value > nums[i] finds it, because the suffix is non-increasing. That makes the prefix as small as possible while still increasing.

Step 3: after the swap the suffix is still non-increasing, i.e. maximal. Reversing makes it minimal, giving the smallest arrangement of the remaining values. Prefix minimally increased plus suffix minimised is precisely the next permutation.

If step 1 finds no such i (the array is fully descending, the last permutation), then i == -1 and step 3 reverses the whole array — wrapping around to the first permutation, which is exactly what the problem specifies.

The variant map

Variant	The technique	Canonical problem
All permutations	used array, loop from 0	46
With duplicates	Sort + skip when not used[i-1]	47
In place, no extra array	Swap-based recursion	46 (alternative)
Next in lexicographic order	Pivot, swap, reverse	31
Previous permutation	Mirror every comparison	556-adjacent
k-th permutation directly	Factorial number system	60
Permutations of a string with constraints	Same template, prune early	784 · 267

LC 60 does not use backtracking at all

Permutation Sequence asks for the k-th permutation of 1..n directly. Generating all of them is $O(n!)$ and hopeless for n = 9.

Instead, use the factorial number system. With n digits there are (n-1)! permutations starting with each possible first digit, so k // (n-1)! selects the first digit outright. Remove it, set k %= (n-1)!, and repeat.

That is $O(n^2)$ (the removal from a list dominates) and never enumerates anything. The lesson generalises: “give me the k-th X” is usually arithmetic on the counting structure, not enumeration.

Practice — real LeetCode problems

LC 46 — Permutations · Medium

Problem. Given an array nums of distinct integers, return all possible permutations in any order.

Constraints. 1 <= len(nums) <= 6, -10 <= nums[i] <= 10, all distinct.

Examples. [1,2,3] gives all 6 permutations · [0,1] gives [[0,1],[1,0]] · [1] gives [[1]]

Why this test sorts the output

The problem accepts the permutations in any order, so the test sorts the result before comparing. Your enumeration order does not matter — only that you produce exactly the right set.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Standard backtracking. At each depth, try every element not already on the path. When the path reaches full length, record a copy.

Time $O(n \cdot n!)$ — optimal, since there are $n!$ outputs of length n. Space $O(n)$ for the recursion and path, excluding the output.

The structural point worth stating: combinations use a start index, permutations use a used array. With combinations, [1,2] and [2,1] are the same answer, so you only ever move forward. With permutations they are different answers, so you must be able to reach back to earlier elements — hence the loop from 0 and the need to track consumption separately.

Note the three paired lines. Both used[i] and path must be restored, and the most common bug is restoring one but not the other.

Follow-ups you should expect:

• “With duplicates (LC 47)?” Sort and add the skip rule — next problem.
• “Do it without the used array.” The swap-based version shown above: swap into position, recurse, swap back. Less memory, different output order, and it does not adapt to duplicates as cleanly.
• “Iteratively?” Start from [[]] and, for each element, insert it at every position of every partial permutation built so far.
• “Just the k-th one (LC 60)?” Factorial number system, no enumeration.
• “Why is exponential acceptable here?” The output itself is $n!$; you cannot do better than producing it.

LC 47 — Permutations II · Medium

Problem. Given a collection of numbers that may contain duplicates, return all unique permutations in any order.

Constraints. 1 <= len(nums) <= 8, -10 <= nums[i] <= 10.

Examples. [1,1,2] gives [[1,1,2],[1,2,1],[2,1,1]] — three, not six · [1,2,3] gives all 6

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Duplicates create identical permutations from distinct positions. The fix is to impose a canonical order on equal values: within any run, they must be consumed left to right. Then each distinct arrangement has exactly one generating path.

Time $O(n \cdot n!)$ worst case (all distinct); far fewer branches when duplicates are present, since the skip prunes whole subtrees. Space $O(n)$.

Both parts are essential:

• Sorting makes equal values adjacent, which is what nums[i] == nums[i-1] relies on. Without it the rule never triggers and duplicates slip through.
• not used[i - 1] is the correct direction, for the reason derived in the note above. This is the single most-misremembered line in backtracking, and it is worth being able to explain rather than recall.

[1,1] giving exactly [[1,1]] is the minimal test: the naive template returns it twice.

An alternative that avoids the reasoning entirely: generate all permutations and deduplicate with a set of tuples. It is correct, and worth mentioning — but it wastes work generating duplicates only to discard them, and uses $O(n!)$ extra memory. The skip rule prunes them before they are built.

Follow-ups you should expect: “Why not used[i-1]?” — the most likely question; derive it. “Could you use a Counter instead?” — yes, and it is arguably cleaner: recurse over distinct values with remaining counts, which needs no sorting and no used array. Worth offering. “How many unique permutations are there?” — $n! / \prod(c_i!)$ for value multiplicities c_i. “Same idea for subsets (LC 90)?” — yes, the identical skip rule.

LC 31 — Next Permutation · Medium

Problem. Rearrange nums into the next lexicographically greater permutation. If no greater permutation exists, rearrange into the lowest (ascending) order. Must be done in place with $O(1)$ extra memory.

Constraints. 1 <= len(nums) <= 100, 0 <= nums[i] <= 100.

Examples. [1,2,3] gives [1,3,2] · [3,2,1] gives [1,2,3] (wraps) · [1,1,5] gives [1,5,1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Pivot, swap, reverse. The full justification is in the note above; the summary is that the suffix after the pivot is already maximal, so the pivot is the rightmost place an increase is possible, and after swapping in the smallest larger value the suffix must be minimised.

Time $O(n)$ — three linear scans. Space $O(1)$, genuinely in place.

The test cases map onto the distinct behaviours:

• [1,2,3] gives [1,3,2] — pivot at index 1, the ordinary case.
• [3,2,1] gives [1,2,3] — fully descending, so i == -1, step 2 is skipped and step 3 reverses everything. The wrap-around falls out of the algorithm with no special case, which is the elegant part.
• [1,1,5] gives [1,5,1] — duplicates; the nums[j] <= nums[i] comparison must be non-strict when scanning for j so it skips over equal values and finds a genuinely larger one.
• [2,3,1] gives [3,1,2] — pivot at index 0, and the suffix [3,1] reverses to [1,2] after the swap.

The comparisons in steps 1 and 2 are worth care: step 1 uses >= (skip non-ascending pairs) and step 2 uses <= (skip values not strictly greater). Making either strict or non-strict incorrectly breaks the duplicate cases while leaving the distinct-value cases working — so [1,1,5] is the test that catches it.

Follow-ups you should expect: “Previous permutation?” — mirror every comparison. “Generate all permutations by repeated application?” — start from the sorted array and apply n! times; a neat $O(1)$-space enumerator. “Next greater element with the same digits (LC 556)?” — this exact algorithm on the digit array, plus an overflow check. “Why is it $O(n)$ and not $O(n \log n)$?” — no sorting is needed; the suffix is already sorted descending by construction.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 784 is a permutation problem that is really a subset problem

Letter Case Permutation asks for every combination of upper/lower case. Despite the name, each letter independently has two choices and digits have one — so it is a binary choice per position, which is the subsets shape, not the arrangements shape. There is no reordering at all.

Reading past the title to the actual structure is the skill. “Permutation” in a problem name does not always mean permutation.

6 problems

0 easy5 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○31Next PermutationmediumPivot, swap, reverse -- $O(n)$, $O(1)$ space
• ○46Permutationsmedium`used` array, loop from 0 -- no `start` indexNeetCode 150LeetCode Top Interview 150
• ○47Permutations IImediumSort + skip when `not used[i-1]`
• ○556Next Greater Element IIImediumLC 31 on digits, plus a 32-bit overflow check
• ○784Letter Case PermutationmediumBinary choice per letter; digits are fixed
• ○60Permutation SequencehardFactorial number system -- arithmetic, not enumeration

Interview follow-ups

They ask	What they’re checking	The answer
“Why no start index?”	The core distinction	Order matters, so earlier elements must remain reachable; consumption is tracked by used instead
“Why not used[i-1]?”	Whether you derived it	It forces equal values to be consumed left to right, so each distinct arrangement has exactly one generating path
“Can you avoid the used array?”	Flexibility	The swap-based recursion; less memory, different order, does not extend cleanly to duplicates
“How many unique permutations?”	Combinatorics	$n! / \prod(c_i!)$ over value multiplicities
“Why is exponential time acceptable?”	Judgement	The output is $n!$ items, so $O(n \cdot n!)$ is optimal
“Get the k-th without enumerating?”	Breadth	Factorial number system: k // (n-1)! picks each digit in turn
“Prove next-permutation is correct”	Rigour	The suffix after the pivot is maximal, so the pivot is the rightmost increasable index; then minimise the suffix

Edge-case checklist

• Single element — one permutation; LC 31 returns it unchanged.
• Two elements — the smallest case where ordering is visible.
• All identical — [1,1] gives exactly one unique permutation.
• Fully descending (LC 31) — [3,2,1]; i == -1 and the whole array reverses.
• Fully ascending (LC 31) — only the last two elements swap.
• Duplicates with LC 31 — [1,1,5]; the <= in the j scan matters.
• Negative values — legal in 46/47; nothing assumes positivity.
• Forgetting to reset used[i] — silently yields too few permutations.
• Recording path instead of list(path) — yields a list of empty lists.

Self-check

pch.quizTag Permutations — self-check

1. Why can't permutations use the `start` index that subsets use?

   A Because permutations are longer B Because order matters and every element must be used — a start index deliberately forbids revisiting earlier indices, which is exactly what a permutation needs to do C Because duplicates must be skipped D They can; the start index works for both
   pch.quizShowAnswer

   B — Because order matters and every element must be used — a start index deliberately forbids revisiting earlier indices, which is exactly what a permutation needs to do — Subsets need each element considered once, so `start` prevents re-picking. Permutations need every index available at every depth, which is what the `used` array provides.

2. In LC 47, what does the condition `nums[i] == nums[i-1] and not used[i-1]` actually enforce?

   A That duplicates never appear in the output list B That within a run of equal values, they are consumed in a fixed order — so the second copy may not start a branch while the first is still unused C That the array stays sorted D That each value is used at most once
   pch.quizShowAnswer

   B — That within a run of equal values, they are consumed in a fixed order — so the second copy may not start a branch while the first is still unused — It does not forbid repeated values — [1,1,2] is a valid output. It forbids consuming them out of order, because that branch is a relabelling of one already explored.

3. Is the flipped condition `used[i-1]` wrong?

   A Yes — it produces almost no output B No — it fixes the opposite consumption order within each run and is equally correct; what is mandatory is the sort plus the equality guard, not a particular spelling of the boolean C Yes — it produces duplicates D It only works for arrays of length 3
   pch.quizShowAnswer

   B — No — it fixes the opposite consumption order within each run and is equally correct; what is mandatory is the sort plus the equality guard, not a particular spelling of the boolean — Verified against itertools.permutations on several multisets: both spellings emit exactly the distinct arrangements. Remembering the *reason* (fix one order per run) beats memorising the boolean.

4. You forget to sort before the duplicate-skip. What happens?

   A A crash on the first comparison B Equal values are no longer adjacent, so `nums[i] == nums[i-1]` never fires and duplicates come through — `[1,2,1]` emits each distinct arrangement twice C The output is sorted anyway D Nothing; the skip works regardless of order
   pch.quizShowAnswer

   B — Equal values are no longer adjacent, so `nums[i] == nums[i-1]` never fires and duplicates come through — `[1,2,1]` emits each distinct arrangement twice — The skip rule is entirely positional — it compares neighbours. Sorting is what makes 'neighbour' mean 'same value', so it is part of the algorithm rather than presentation.

5. Why is `out.append(list(path))` rather than `out.append(path)`?

   A For type consistency B Because `path` is one list mutated throughout the traversal — storing the reference means every recorded permutation is the same object, which the un-choose `pop()` then empties C Because append is faster on a copy D It makes no difference here
   pch.quizShowAnswer

   B — Because `path` is one list mutated throughout the traversal — storing the reference means every recorded permutation is the same object, which the un-choose `pop()` then empties — The single most common backtracking bug, in permutations and everywhere else. The output is a snapshot; the path is a workspace.

6. Constraints say `n <= 8`. What is that telling you?

   A That an O(n²) solution is expected B That factorial output is expected and acceptable — 8! is 40,320, and there is no way to beat exponential time when the answer itself has n! entries C That the input may contain duplicates D That recursion depth is a concern
   pch.quizShowAnswer

   B — That factorial output is expected and acceptable — 8! is 40,320, and there is no way to beat exponential time when the answer itself has n! entries — You cannot enumerate n! things in less than O(n!) time. Tiny constraints are the signal that enumeration is the intended solution — which also means the k-th permutation (LC 60) must NOT enumerate.

Recall card

• Cue — “all orderings / arrangements / permutations”, order matters, every element used. Tiny constraints (n <= 8).
• Template — a used[] array, not a start index: every index is available at every depth. Choose → recurse → un-choose, and out.append(list(path)) — the copy is mandatory.
• Duplicates (LC 47) — sort, then skip nums[i] == nums[i-1] and not used[i-1]. The rule is “fix one consumption order within each run of equal values”; the mirrored spelling used[i-1] is equally valid, the sort is not optional.
• Swap-based variant — one shared array, swap and swap back; $O(n)$ extra space instead of $O(n \cdot n!)$.
• Cost — $O(n \cdot n!)$ time, and that is optimal: the output alone is $n!$ entries.
• Next permutation (LC 31) — find the rightmost a[i] < a[i+1] (the pivot), swap with the rightmost value greater than it, reverse the suffix. $O(n)$ time, $O(1)$ space, no recursion.
• k-th permutation (LC 60) — do not enumerate; use factorial-base arithmetic to pick each digit directly.

Recap

• Permutations use a used array and a loop from 0; combinations use a start index. That is the whole structural difference.
• Copy on record, and pair every choose with its un-choose — both path and used.
• For duplicates: sort, then skip nums[i] when it equals nums[i-1] and used[i-1] is False. That fixes a left-to-right consumption order within each run, so each arrangement is generated once. A Counter over distinct values is an equally good alternative.
• $O(n \cdot n!)$ is optimal for enumeration — the output is that large.
• Next permutation is a different problem: pivot, swap, reverse, in $O(n)$ and $O(1)$ space, with the wrap-around handled automatically.
• “Give me the k-th” is usually arithmetic on the counting structure, not enumeration.

Next: Backtracking — the same skeleton applied to constrained search, where pruning is what makes it feasible.