Permutations

Swap-based backtracking fixes one array position at a time: swap a remaining value into start, recurse, then repeat that swap to give the caller its exact array back. That single restore line can undo the effect of an arbitrarily large recursive subtree. With n distinct values, the search emits n! orderings.

Think of each recursive call as borrowing the array. It may rearrange the suffix as much as it needs, but it must return the array in the order it received. That promise is what lets the caller try its next choice without rebuilding any state.

Use the swap form when you need every ordering and may mutate a working array during the search. If intermediate mutation is awkward or forbidden, a path + remaining version is often easier to reason about, though it allocates more temporary arrays.

How the recursive choice works

Suppose nums = [1, 2, 3] and the first call is backtrack(0). Position 0 has three candidates. The loop tries each one in order:

1. Keep 1 at position 0 with a self-swap, then recurse on [2, 3].
2. Swap 2 into position 0, then recurse on [1, 3].
3. Swap 3 into position 0, then recurse on [2, 1].

Inside the first branch, backtrack(1) has two choices. It first keeps 2 in position 1, which leaves only one choice at the next depth and emits [1, 2, 3]. After returning, it swaps position 1 with itself to restore the caller. It then swaps 3 into position 1 and emits [1, 3, 2].

The important detail is what happens before the root loop advances to its second choice. Every inner swap has already been undone, and the root's self-swap is undone too. The array is [1, 2, 3] again. The animation pauses here to compare the saved caller snapshot with the returned row. Only after it shows [1, 2, 3] = [1, 2, 3] does the loop swap positions 0 and 1 for the next root branch.

The animation keeps stable identities on the tokens, even when two values are equal. That lets the movement show which source position was chosen without changing the code's ordinary number-array model.

Why the count is n factorial

At depth 0, there are n choices for the first position. Once that position is fixed, depth 1 has n - 1 choices. The process continues until the final position has one choice:

n * (n - 1) * ... * 1 = n!

For three items, the factor strip reads 3 * 2 * 1 = 6. It is not an estimate. Each factor corresponds to one recursion depth, and each completed path through those choices reaches exactly one base case.

The base case copies the current array into result. The copy matters because the same mutable nums array will keep changing as recursion unwinds. Appending the array reference itself would make every result entry point to one object. At the end, all entries would show the same restored order.

The backtracking invariant

For a call backtrack(start), the invariant is:

Before each loop iteration, nums has exactly the order that this call received from its caller.

The forward swap creates one child state. The recursive call is free to perform many deeper swaps, but it must restore its own entry state before returning. The reverse swap at the current depth then restores the current caller's entry state.

This nesting is why one line can undo an arbitrarily large subtree. The line does not reverse every descendant operation itself. Each descendant already fulfilled the same contract on its way out.

Remove the reverse swap and the loop still reaches the base case n! times, but later sibling branches begin from mutated arrays. With three or more distinct values, some orderings repeat while others disappear. Small inputs can survive by coincidence: [1, 2] still emits both orders, because its first subtree only self-swaps and the second root choice still starts from [1, 2]. Backtracking requires restoration, not merely recursion.

What the no-restore variant proves

The No restore control removes only the second swap. On [1, 2, 3], the first root subtree returns [1, 3, 2] instead of the caller's [1, 2, 3]. The next sibling therefore begins from the wrong row.

The loop still reaches six leaves, but the ledger contains only four unique orderings:

• [1, 2, 3]
• [1, 3, 2]
• [3, 1, 2]
• [3, 2, 1]

The first two appear twice, while [2, 1, 3] and [2, 3, 1] never appear. This is the visible consequence of breaking the caller contract: six base-case visits do not guarantee six permutations.

Permutations step by step

Here is the complete restored run for the default [1, 2, 3] input:

1. Root choice 1: the root self-swaps, then depth 1 keeps 2. Depth 2 keeps 3, so the first copied leaf is [1, 2, 3].
2. The depth-2 and depth-1 self-swaps undo. Depth 1 swaps 3 into slot 1 and copies [1, 3, 2]. Every swap then unwinds until the root row is [1, 2, 3] again.
3. Root choice 2: swap positions 0 and 1 to get [2, 1, 3]. Keeping 1 in slot 1 emits [2, 1, 3]; swapping 3 into slot 1 emits [2, 3, 1].
4. That subtree unwinds to [1, 2, 3]. Root choice 3 swaps positions 0 and 2 to get [3, 2, 1].
5. Keeping 2 in slot 1 emits [3, 2, 1]; swapping positions 1 and 2 emits [3, 1, 2].
6. The final reverse swaps restore [1, 2, 3], and the root returns with six copied outputs.

The same run summarized by root choice is:

The output ledger groups leaves by the stable token chosen for the first position. Each group contains (n - 1)! outputs. The groups make the first factor visible, while the call stack shows which remaining factor is active.

Self-swaps are genuine algorithm steps. When i === start, the item is already in the required slot, so swapping it with itself leaves the array unchanged. Keeping that case in the loop gives every depth one uniform rule and avoids a special branch.

Duplicate values are a different problem

The simple algorithm treats positions as distinct choices. With [1, 1, 2], the two 1 tokens have different source identities, so the search still visits 3! = 6 positional leaves. Their values produce only three unique sequences:

• [1, 1, 2]
• [1, 2, 1]
• [2, 1, 1]

Each appears twice. The duplicate preset keeps all six appends and connects a repeated value sequence to its earlier match. This is a diagnosis, not hidden de-duplication.

If a problem asks for unique permutations, use a variant that skips equal choices at the same recursion depth, commonly with a small used set for that loop. Do not merely place the final outputs in a set after generating them unless the wasted factorial work is acceptable.

Time and space complexity

The in-place swaps keep the search state compact, but they do not make materializing every permutation cheap. Output size already forces Theta(n * n!) work and storage. That growth is why the interactive canvas limits inputs to four items; the algorithm itself is not limited to four.

Even the lesson's four-item run needs about 2 minutes 35 seconds to show its 24 leaves at teaching pace. At n = 12, there are already 12! = 479,001,600 leaves before accounting for the cost of copying twelve values into each output.

Small permutation searches appear in brute-force traveling-salesperson routes, letter-arrangement generators, and short scheduling problems. In practice, the useful question is usually whether n is genuinely small or whether constraints can prune most branches. If neither is true, generating every ordering is rarely a workable plan.

Edge cases

• A single item has one permutation. The trace performs one self-swap, reaches the base case, copies the item, and restores the root.
• The empty array is often defined to have one permutation, the empty ordering. This lesson accepts one to four items so every frame has a visible token; production code may choose to support the mathematical empty case.
• Negative values and repeated values are valid array entries. Values do not affect traversal order; positions do.
• Traversal order depends on the loop order. Reversing the loop still generates the same set for distinct inputs, but the ledger order changes.
• The result must store a copy. Python uses nums.copy(); JavaScript uses [...nums].

Common mistakes

• Forgetting the reverse swap. The next sibling inherits a mutated array. With three or more distinct values, some orderings repeat and others go missing.
• Appending the mutable array itself. Every result aliases the same object and later swaps rewrite earlier answers.
• Advancing the wrong boundary. Recursion must call backtrack(start + 1). Advancing i confuses the loop cursor with the fixed-prefix length.
• Using a global used set. A token used in one completed branch must be available in its siblings. Duplicate skipping, when needed, is scoped to one depth.
• Calling every leaf unique. n! counts positional leaves. It equals the number of unique value sequences only when the input values are distinct.

Whichever formulation you use, the contract stays the same: make one choice, recurse, and leave the caller's state exactly as you found it.