Permutations
mediumEach position picks one of the remaining values by swapping it forward. Undoing the swap restores the array exactly, so one array serves the entire search instead of n! copies.
O(n × n!)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How permutations works
A permutation fixes positions one at a time. Position 0 can hold any of the n values; whichever it takes, position 1 chooses among the n − 1 that remain, and so on - which is exactly why there are n! arrangements. The swap trick makes choosing free: swapping a[i] forward to position start both selects the value and keeps the not-yet-used values packed in the suffix.
The undo is the mirror image of the choose. Swapping the same two positions back restores the array exactly as it was, so one working array serves the entire search - no visited flags, no remaining-values list, no copies except the n! recorded answers. This is choose-explore-undo where the undo is a single swap, the cheapest possible restoration.
There is no pruning here, because nothing can be rejected - every branch ends in a valid permutation. What the pattern buys instead is memory discipline and a template: add a constraint test before the recursive call and the same skeleton solves N-Queens. Factorial growth is the real limit - 4 values mean 24 outputs, 10 mean 3,628,800 - which is why the engine caps input at 5.
Step by step
- Run [1, 2, 3]. Position 0 keeps 1 in place - a swap with itself - and recurses to arrange positions 1 and 2.
- Deeper calls fix the suffix: keeping 2 records 123, then swapping 2 and 3 records 132. Each recording copies the array.
- Back at the top, the undo swap restores [1, 2, 3], and position 0 swaps 2 forward: 213 and 231 follow.
- The third choice swaps 3 to the front. Notice the tail order flips: 321 comes before 312, because the swap disturbed the suffix.
- Six permutations - exactly 3! - arrive in the order 123, 132, 213, 231, 321, 312, which is not lexicographic.
- After the final undo the working array is [1, 2, 3] again, untouched - proof that every swap was matched by its reverse.
Complexity
| Worst case time | O(n × n!) |
|---|---|
| Space | O(n) |
There are n! outputs, so no algorithm that lists them can be faster.
Reference implementation
Python
def permutations(a):
out, n = [], len(a)
def backtrack(start):
if start == n:
out.append(a[:]) # copy - a keeps mutating
return
for i in range(start, n):
a[start], a[i] = a[i], a[start] # choose
backtrack(start + 1) # explore
a[start], a[i] = a[i], a[start] # undo
backtrack(0)
return outJavaScript
function permutations(a) {
const out = [], n = a.length;
(function backtrack(start) {
if (start === n) { out.push([...a]); return; }
for (let i = start; i < n; i++) {
[a[start], a[i]] = [a[i], a[start]];
backtrack(start + 1);
[a[start], a[i]] = [a[i], a[start]];
}
})(0);
return out;
}Worth noticing
Swap-in-place, then swap back
Each position picks one of the remaining values by swapping it forward. Undoing the swap restores the array exactly, so one array serves the whole search instead of n! copies.
Why the result must be copied
`a` keeps mutating after a permutation is recorded. Appending the array itself rather than a copy leaves every entry in the output pointing at the same, final array - a genuinely common bug.
n! is not a complexity you optimise away
There are n! permutations, so any algorithm that lists them takes at least that long. 10 items is 3.6 million; 15 is a trillion. If a problem needs all permutations, the real question is whether you can avoid needing them.
Common pitfalls
- Recording the array itself instead of a copy. The array keeps mutating, so the output ends up holding n! references to one identical final state - append a[:] or [...a].
- Forgetting the second swap. Without the undo, sibling branches inherit a scrambled prefix and the output contains repeats and omissions - and nothing crashes to warn you.
- Starting the loop at 0 instead of start. Positions already fixed get re-chosen, producing duplicated and missing arrangements.
- Expecting sorted output. Swap-based generation emits 321 before 312; if lexicographic order matters, sort afterwards or use the next-permutation technique instead.
- Running it on big inputs. n = 10 already means 3,628,800 outputs; if the task only needs one best arrangement, search with pruning or dynamic programming instead.
Where it is used
- Exhaustive baselines for ordering problems - brute-forcing the travelling salesman on a handful of cities means trying all n! route orders.
- Testing order-sensitive systems, where every possible arrival order of n events or messages must be exercised.
- Anagram and word-puzzle generation, where each rearrangement of letters is a candidate to check against a dictionary.
- LeetCode 46 verbatim, and the base pattern behind the duplicate-handling and letter-case interview variants.
Frequently asked questions
What is the time and space complexity of generating permutations?
Time is O(n × n!): there are n! permutations and each is copied in O(n) when recorded. That is optimal - no algorithm listing n! outputs can beat the size of its own output. Space beyond the output is O(n): one working array and a recursion stack n deep.
What is the difference between permutations and combinations?
Permutations care about order, combinations do not. Picking two of [1, 2, 3] gives 6 permutations (12, 21, 13, 31, 23, 32) but only 3 combinations (12, 13, 23). The counts are n!/(n−k)! versus n!/(k!(n−k)!). This module generates full-length permutations, where k = n.
Why do all my permutations look the same?
Almost always the copy bug: out.append(a) stores a reference, not a snapshot, and a is restored to its original order by the time you read the results. Append a[:] in Python or [...a] in JavaScript. The insight panel calls this out because it is a genuinely common bug.
Does this handle duplicate values?
No - positions are treated as distinct, so [1, 1, 2] produces 6 outputs of which only 3 differ. Removing duplicates needs an extra rule, such as skipping a value already tried at the current position; that variant is the usual follow-up interview question.