Permutations

Same template, different "choices" function

Permutations use the identical choose → explore → un-choose skeleton from Subsets & Combinations, but the definition of "what am I allowed to pick next" changes. In subsets/combinations you only ever look forward from a start index — an element you skip is skipped for good in that branch. In permutations, order matters, so at every position you're allowed to pick any element you haven't used yet, regardless of its index. That's the fundamental structural shift: the branching factor at depth d is n − d (whatever's unused), not "whatever's left after some index."

Because a permutation is only valid when it uses every element, you snapshot the result only at the leaves (len(path) == n), unlike subsets where every node of the tree is a valid answer.

Approach 1: a used[] boolean array

The most direct implementation tracks which indices are already in the current path:

Note there are now two pieces of state to undo on the way back up — the path list and the used marker — not just one. Forgetting either one corrupts the search identically to forgetting path.pop() in the subsets template.

Approach 2: in-place swapping

An alternative avoids the extra used[] array (and the x not in path linear scan some naive implementations mistakenly use) by partitioning the array in place: everything before index i is "fixed" (part of the current permutation prefix), everything from i onward is "still available." At each step, swap each available element into position i, recurse, then swap back.

This is the same decision tree as the used[] version — same n! leaves — but trades an O(n) auxiliary array for two O(1) swaps per call, at the cost of being slightly harder to adapt when the duplicate-skipping rule below is needed (skipping requires the array to be sorted, and swapping destroys the original order as you go).

Approach	Extra space	Handles duplicates cleanly?	Preserves original array order for skip-checks?
used[] boolean array	O(n)	Yes — sort once up front, order never changes	Yes
In-place swap	O(1) beyond recursion stack	Awkward — swapping destroys sorted order mid-recursion	No

Default to the used[] array in interviews unless you're specifically asked to optimize space and the input has no duplicates — the swap approach's incompatibility with the standard duplicate-skip trick is a real liability, not just a style choice.

Handling duplicates: the same trick, a subtly different condition

Just like Subsets & Combinations, generating permutations from an input with duplicate values (e.g. [1, 1, 2]) naively produces the same output multiple times. The cause is the same: backtracking distinguishes indices, but the problem asks for unique value sequences. Picking the 1 at index 0 then the 1 at index 1 yields [1, 1, 2]; picking them in the opposite index order yields the same list again.

The fix is structurally the same as subsets — sort first, then skip a redundant sibling at the same recursion depth — but the exact guard condition is different, and mixing the two up is a classic interview slip-up.

The invariant

Among equal values, force a canonical usage order. The standard form is left-to-right: whenever you place one of several identical values, always place the leftmost still-available copy first. Any branch that would place a later copy while an earlier identical copy is still free is pruned, because that permutation will already be generated by using the earlier copy at this depth instead.

That invariant is what not used[i - 1] encodes.

Template

For subsets, the guard was i > start and nums[i] == nums[i - 1], because subsets iterate over a shrinking [start, n) range where index order directly encodes "have I already tried this sibling."

For permutations, there's no start index — availability is tracked by used[] — so the guard instead has to reason about whether the identical previous value is currently in the path or not:

Reading the guard, piece by piece

Clause	Meaning
i > 0	There is a previous index to compare against
nums[i] == nums[i - 1]	Same value as the adjacent earlier copy (requires the sort)
not used[i - 1]	That earlier copy is still free — so taking i now would be the "later copy first" branch we forbid

Read not used[i - 1] carefully — it means "the identical previous value is not currently placed." Skipping in that situation avoids re-deriving a permutation you'll reach anyway by using the earlier copy first.

The flip side matters too: if used[i - 1] is True, the earlier copy is already in the path, so taking this next identical copy is the legitimate continuation of the left-to-right order — do not skip.

Walkthrough: [1, 1, 2]

After sorting, indices are 0:1, 1:1, 2:2. Unique answers: [1,1,2], [1,2,1], [2,1,1].

At depth 0 (empty path):

• i = 0 → first 1, allowed. Explore prefix [1].
• i = 1 → second 1, but nums[1] == nums[0] and used[0] is still False → skip. This is the whole point: starting with "the other 1" would duplicate every branch that starts with the first 1.
• i = 2 → 2, allowed. Explore prefix [2].

From prefix [1] (only used[0] = True):

• i = 1 → second 1 is allowed now, because used[0] is True (left-to-right order satisfied) → path [1,1], then only [1,1,2].
• i = 2 → 2 → path [1,2], then [1,2,1].

From prefix [2]:

• Only the two 1s remain; the same left-to-right rule forces index 0 before index 1, producing a single [2,1,1].

Without the guard you'd also explore "start with index-1's 1" and regenerate the same three results a second time.

Why this differs from the subsets guard

	Subsets / combinations	Permutations
Loop range	for i in range(start, n) — only forward	for i in range(n) — any unused index
Availability	Encoded by start	Encoded by used[]
Skip condition	i > start and nums[i] == nums[i - 1]	i > 0 and nums[i] == nums[i - 1] and not used[i - 1]
What "already handled" means	Already tried this value as a sibling in this loop	Already committed to using equal values in left-to-right index order across depths

Subsets forbid re-trying an already-tried sibling in the current loop iteration. Permutations forbid breaking the global placement order among equal values. Same intuition ("one canonical way to pick equals"), different bookkeeping — because permutations track "used" globally across depths, not "start" locally per depth.

Mirror form (optional)

A right-to-left mirror also works: skip when the next identical copy is still free (nums[i] == nums[i + 1] and not used[i + 1]). That forces equal values to be consumed right-to-left instead. Same unique outputs, different branch order. Prefer the left-to-right not used[i - 1] form in interviews — it's the standard people expect and the one that matches most editorial solutions.

Base case stays outside the loop

Keep the len(path) == len(nums) check before the for loop (as in the template). Putting it inside the loop still "works" if you return on the first iteration, but it's an extra recursive call that only exists to snapshot — and it muddies the choose/explore structure.

Complexity analysis

Generating all permutations of n elements is O(n!) — there are exactly n! distinct orderings, each taking O(n) to build/copy, giving a commonly-stated total of O(n · n!). This is the factorial complexity class from Big-O & Complexity Analysis, and it's worth having a gut feeling for how brutal it is: 10! is ~3.6 million, but 15! is already ~1.3 trillion. Any permutation-generation problem with n > ~10 in the constraints is a signal that the intended solution is not "generate every permutation and check it" — it wants a smarter approach (see Permutation Sequence in the problem set below, which never generates a single full permutation).

As with subsets, pruning (early duplicate-skipping, an is_valid check like the one in Beautiful Arrangement) doesn't change the worst-case O(n!) bound but can reduce the actual visited-node count by orders of magnitude when the constraints are restrictive — exactly the same worst-case-vs-practical distinction covered in Subsets & Combinations.

Common pitfalls

• Forgetting to undo used[i]. Symmetric to forgetting path.pop(): if you only undo the path but not the used marker, every element gets permanently "used up" after its first appearance, and you'll silently generate far fewer than n! results (often just one).
• Appending a reference, not a copy. Same bug as in subsets — res.append(path) instead of res.append(path[:]). It's worth internalizing this as the universal backtracking bug, since it recurs in every subtopic in this topic.
• Using the subsets duplicate-skip condition for permutations, or vice versa. i > start (subsets) and not used[i - 1] (permutations) look superficially similar but encode different bookkeeping — one is about loop position, the other about global placement state. Confusing them either under- or over-generates output.
• Inverting the used check. Skipping when used[i - 1] is True (instead of False) flips the invariant and typically produces no permutations of repeated values, because the legitimate left-to-right continuation gets pruned. If your unique-perms output is empty or tiny on inputs like [1,1,2], check this first.
• Mutable default arguments / shared list references across calls. In languages/patterns where a helper function has a default mutable argument (e.g., Python's def dfs(path=[])), that default list is created once and shared across every top-level call to the function, silently accumulating state across unrelated calls. Always initialize mutable state inside the function body or pass it explicitly.
• Reaching for the swap-based approach when duplicates are present. As noted above, in-place swapping actively fights the sort-based duplicate-skip trick. If the problem says "may contain duplicates," default to the used[] array approach.