Permutations and Arrangements

Subsets and combinations use a startstart 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 startstart 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 usedused array template, and why a startstart 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

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]]

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 00 every time — that is the difference from combinations. The usedused array is what prevents reusing an element already on the current path.

An alternative worth knowing is the swap-based version, which permutes the array in place and needs no usedused 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

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 usedused template is the one to default to.

Handling duplicates

For [1, 1, 2][1, 1, 2] the plain template produces [1,1,2][1,1,2] twice, because the two 11s 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

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

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]nums[i] may only be used if its identical left neighbour has already been used on this path.

If used[i-1]used[i-1] is TrueTrue, the predecessor is on the current path, so we are extending the run in canonical order — allowed.
If used[i-1]used[i-1] is FalseFalse, 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.

Flipping the condition to used[i - 1]used[i - 1] produces almost nothing, because the first copy of each run can then never start a path. Sorting is mandatory: without it, equal values are not adjacent and nums[i] == nums[i-1]nums[i] == nums[i-1] never fires.

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 <= 6n <= 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

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

After step 1, the suffix nums[i+1:]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 ii the rightmost position where an increase is possible.

Step 2 puts the smallest available value that is still strictly greater than nums[i]nums[i] into position ii. Scanning from the right and stopping at the first value > nums[i]> 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 ii (the array is fully descending, the last permutation), then i == -1i == -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	`usedused` array, loop from 0	46
With duplicates	Sort + skip when `not used[i-1]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

Practice — real LeetCode problems

LC 46 — Permutations · Medium

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

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

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

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 nn. Space $O(n)$ for the recursion and pathpath, excluding the output.

The structural point worth stating: combinations use a startstart index, permutations use a usedused array. With combinations, [1,2][1,2] and [2,1][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 00 and the need to track consumption separately.

Note the three paired lines. Both used[i]used[i] and pathpath 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 usedused 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) <= 81 <= len(nums) <= 8, -10 <= nums[i] <= 10-10 <= nums[i] <= 10.

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

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]nums[i] == nums[i-1] relies on. Without it the rule never triggers and duplicates slip through.
not used[i - 1]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][1,1] giving exactly [[1,1]][[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 setset 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]not used[i-1]?” — the most likely question; derive it. “Could you use a CounterCounter instead?” — yes, and it is arguably cleaner: recurse over distinct values with remaining counts, which needs no sorting and no usedused array. Worth offering. “How many unique permutations are there?” — $n! / \prod(c_i!)$ for value multiplicities c_ic_i. “Same idea for subsets (LC 90)?” — yes, the identical skip rule.

LC 31 — Next Permutation · Medium

Problem. Rearrange numsnums 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) <= 1001 <= len(nums) <= 100, 0 <= nums[i] <= 1000 <= nums[i] <= 100.

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

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][1,2,3] gives [1,3,2][1,3,2] — pivot at index 1, the ordinary case.
[3,2,1][3,2,1] gives [1,2,3][1,2,3] — fully descending, so i == -1i == -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][1,1,5] gives [1,5,1][1,5,1] — duplicates; the nums[j] <= nums[i]nums[j] <= nums[i] comparison must be non-strict when scanning for jj so it skips over equal values and finds a genuinely larger one.
[2,3,1][2,3,1] gives [3,1,2][3,1,2] — pivot at index 0, and the suffix [3,1][3,1] reverses to [1,2][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][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!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

#	Problem	Difficulty	The twist
46	Permutations	Medium	`usedused` array, loop from 0 — no `startstart` index
47	Permutations II	Medium	Sort + skip when `not used[i-1]not used[i-1]`
31	Next Permutation	Medium	Pivot, swap, reverse — $O(n)$ , $O(1)$ space
784	Letter Case Permutation	Medium	Binary choice per letter; digits are fixed
556	Next Greater Element III	Medium	LC 31 on digits, plus a 32-bit overflow check
60	Permutation Sequence	Hard	Factorial number system — arithmetic, not enumeration

Interview follow-ups

They ask	What they’re checking	The answer
“Why no `startstart` index?”	The core distinction	Order matters, so earlier elements must remain reachable; consumption is tracked by `usedused` instead
“Why `not used[i-1]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 `usedused` 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)!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][1,1] gives exactly one unique permutation.
Fully descending (LC 31) — [3,2,1][3,2,1]; i == -1i == -1 and the whole array reverses.
Fully ascending (LC 31) — only the last two elements swap.
Duplicates with LC 31 — [1,1,5][1,1,5]; the <=<= in the jj scan matters.
Negative values — legal in 46/47; nothing assumes positivity.
Forgetting to reset used[i]used[i] — silently yields too few permutations.
Recording pathpath instead of list(path)list(path) — yields a list of empty lists.

Recap

Permutations use a usedused array and a loop from 0; combinations use a startstart index. That is the whole structural difference.
Copy on record, and pair every choosechoose with its un-chooseun-choose — both pathpath and usedused.
For duplicates: sort, then skip nums[i]nums[i] when it equals nums[i-1]nums[i-1] and used[i-1]used[i-1] is FalseFalse. That fixes a left-to-right consumption order within each run, so each arrangement is generated once. A CounterCounter 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Permutations and Arrangements

What you’ll learn

The cue

The template

Handling duplicates

Complexity, and what it implies

Next permutation — pivot, swap, reverse

The variant map

Practice — real LeetCode problems

LC 46 — Permutations · Medium

LC 47 — Permutations II · Medium

LC 31 — Next Permutation · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?