Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return every ordering of the array. Unlike subsets/combinations, ORDER matters and every element is used exactly once — so there is NO start index. Instead track which elements are already in the path with a `used[]` boolean array (or a set), loop `i` from 0 every level, skip used elements, choose → recurse → un-choose. There are n! permutations, so the answer is O(n · n!).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know that order-matters problems drop the start index in favour of a used[] set, and whether you correctly restore BOTH the path and the used flag on backtrack. Bonus: recognising n! as the lower bound so O(n · n!) is optimal.
Where candidates slip
Keeping a start index (which produces combinations, not permutations), forgetting to reset `used[i] = false` after recursion (so later branches think the element is taken), or recording partial paths instead of only full-length ones.
How to stand out
Contrast permutations vs subsets explicitly — 'order matters, so no start index; I track used elements instead'. State n! as the lower bound, write clean choose/explore/un-choose, and mention the in-place swap variant that avoids the used[] array.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:At each level we may pick ANY element not yet used (no start index). Only the full-length leaves are recorded. Each downward edge is a 'choose'; returning up is an 'un-choose' that frees the element again.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Backtracking with a used[] Set (Optimal)
1Hint 1Explore hintHide hint
There are n! permutations. Think of filling positions left to right: position 0 can be any element, position 1 any of the remaining, and so on. What do you need to remember to know which elements remain?
2Hint 2Explore hintHide hint
Unlike subsets, order matters, so don't use a start index — at every level loop `i` from 0 and skip elements already placed. A boolean `used[]` (or a set) tracks what's in the current path.
3Hint 3Explore hintHide hint
Choose: mark `used[i] = true` and append nums[i]. Explore: recurse. Un-choose: pop AND set `used[i] = false`. Record a copy only when the path length equals n.
A · Core idea
Fill the permutation position by position. At each call, loop i over all indices from 0; if nums[i] is already in the path (used[i] is true) skip it, otherwise choose it (mark used, append), explore by recursing, then un-choose (pop and unmark). When the path reaches length n we've placed every element, so we record a copy and return.
Why there is no start index — the key contrast with Subsets. In subsets/combinations the start index enforces non-decreasing order so {1,2} and {2,1} aren't both emitted. But for permutations [1,2] and [2,1] are different valid answers — we want both. So we must allow each position to draw from any element, which means looping from 0 every level. The price of dropping the start index is that we can no longer use position to know what's been used; we need explicit bookkeeping, which is exactly what used[] provides.
Why `used[]` is the right bookkeeping. Each element must appear exactly once per permutation. used[i] answers 'is nums[i] already in the current path?' in O(1). When it's true we continue, guaranteeing no element is placed twice. A set of values works too when elements are distinct, but a boolean array indexed by position is cleaner and also handles the duplicate-value case the moment you graduate to Permutations II.
Why you must restore BOTH on un-choose. The single most common bug here is asymmetric backtracking. Choosing does two things — used[i] = true and path.append — so un-choosing must undo both: path.pop() and used[i] = false. Restore only the path and the element stays marked 'used' forever, so every later branch wrongly believes it's unavailable and you lose whole swaths of permutations. The choose and un-choose steps must be mirror images.
Why we record only at a full-length leaf. A permutation, by definition, is a complete arrangement of all n elements. Partial paths like [1,2] (when n = 3) are not answers — they're just internal nodes on the way to [1,2,3] and [1,3,... wait, that branch]. So the base case is len(path) == n, and we snapshot path[:] there. Appending the live path instead would store a reference that the subsequent pops mutate, corrupting every saved permutation.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3]Interactive diagram
Choose / explore / un-choose for [1,2,3]
path=[], used={}Going down marks an element used; coming back up frees it. Only the length-3 leaves are recorded as permutations.
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]C · Code with teaching comments
D · Why it works and complexityO(n · n!) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Permutations vs Subsets is the cleanest illustration of the two backtracking 'modes': when order is irrelevant, a start index moves forward only and needs no membership tracking; when order matters, you drop the start index and pay for a used[] set. Knowing which mode a problem is in — by asking 'is [1,2] the same as [2,1] here?' — tells you instantly which skeleton to write.
ComplexityO(n · n!) time, O(n) space — There are n! leaves (complete permutations) and the tree has fewer than n·n! internal nodes total. At each of the n! leaves we copy a length-n path, costing O(n). So total time is O(n · n!). Extra space beyond the output is the recursion depth (n), the path (n), and used[] (n) — all O(n).
E · Edge cases and pitfalls6nums = [1] — Root chooses 1 → path length 1 == n → record [1]. Returns [[1]]. The single-element base case.Explore edge casesHide edge cases
Edge cases handled
nums = [1]Root chooses 1 → path length 1 == n → record [1]. Returns [[1]]. The single-element base case.nums = [0, 1]Produces [0,1] and [1,0]. The used[] check (not a truthiness test) means element 0 is handled correctly.
Pitfalls
- Keeping a start index — turns the output into combinations (only [1,2], never [2,1]).
- Forgetting `used[i] = false` on backtrack — the element stays marked and later branches lose permutations.
- Recording partial paths instead of only length-n leaves — emits incomplete arrangements.
- Appending `path` instead of `path[:]` — all stored permutations mutate to the same list.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<Integer>> permute(int[] nums) { List<List<Integer>> results = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(nums, used, new ArrayList<>(), results); return results;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Keeping a start index (gives combinations)
A start index forces forward-only picks, so you'd produce [1,2] but never [2,1]. Permutations need every ordering, so loop from 0 and track used elements instead.
Explore the code comparisonHide the code comparison
Keeping a start index (gives combinations)
A start index forces forward-only picks, so you'd produce [1,2] but never [2,1]. Permutations need every ordering, so loop from 0 and track used elements instead.
Don't write this
def backtrack(start, path):
if len(path) == len(nums):
results.append(path[:]); return
for i in range(start, len(nums)): # start index → combinations!
path.append(nums[i])
backtrack(i + 1, path)
path.pop()Write this instead
def backtrack(path):
if len(path) == len(nums):
results.append(path[:]); return
for i in range(len(nums)): # from 0, with used[]
if used[i]:
continue
used[i] = True; path.append(nums[i])
backtrack(path)
path.pop(); used[i] = False2Forgetting to reset used[i]
Choosing sets `used[i] = True`. If un-choose pops the path but doesn't reset the flag, the element stays 'taken' for every sibling and ancestor branch, silently dropping most permutations.
Explore the code comparisonHide the code comparison
Forgetting to reset used[i]
Choosing sets `used[i] = True`. If un-choose pops the path but doesn't reset the flag, the element stays 'taken' for every sibling and ancestor branch, silently dropping most permutations.
Don't write this
used[i] = True; path.append(nums[i])
backtrack(path)
path.pop() # used[i] never reset!Write this instead
used[i] = True; path.append(nums[i])
backtrack(path)
path.pop(); used[i] = False # restore BOTH3Storing the live path reference
`results.append(path)` stores the same list; later pops mutate it, so every permutation ends up identical. Snapshot with `path[:]`.
Explore the code comparisonHide the code comparison
Storing the live path reference
`results.append(path)` stores the same list; later pops mutate it, so every permutation ends up identical. Snapshot with `path[:]`.
Don't write this
if len(path) == len(nums):
results.append(path) # reference to a mutating list
returnWrite this instead
if len(path) == len(nums):
results.append(path[:]) # snapshot copy
returnRevise
Carry the pattern into the interview
Pattern to remember
Backtracking with a used[] set, no start index (choose → explore → un-choose)
Code pattern to memorize
def backtrack(path):
if len(path) == len(nums): results.append(path[:]); return
for i in range(len(nums)): # always from 0 — order matters
if used[i]: continue # skip elements already in the path
used[i] = True; path.append(nums[i]) # choose
backtrack(path) # explore
path.pop(); used[i] = False # un-choose (restore BOTH)Rules to remember
- 1No start index — permutations care about order, so loop
ifrom 0 at every level (the opposite of subsets/combinations). - 2Track membership with
used[](or a set) andcontinueon used elements — that's what stops an element appearing twice in one permutation. - 3Record only at a complete leaf (
len(path) == n) — every permutation uses all n elements, so partial paths aren't answers. - 4On un-choose you must restore both
path.pop()andused[i] = false— forgetting the second leaves the element permanently marked. - 5Append a copy
path[:]— the shared path keeps mutating as you backtrack and would corrupt stored permutations. - 6There are exactly n! permutations —
O(n · n!)is optimal; you cannot beat the output size.
Use this pattern when
- Asked for **all orderings / arrangements** where sequence matters
- Every element must be used exactly once (full-length results only)
- [1,2,3] and [3,2,1] are **different** valid answers
- Anagrams, seating arrangements, ordering tasks under no extra constraint
Choose another pattern when
- Order does **not** matter → that's Subsets/Combinations (use a start index instead of used[])
- Only the **count** of orderings is needed → it's just n!, no enumeration
- Input has duplicates and you must dedup → Permutations II (sort + skip same-level repeats)
- n is large (> ~10–12) → n! explodes; the problem can't want full enumeration
Interview takeaway
Permutations is the 'order matters' member of the backtracking family. The defining edit vs Subsets is dropping the start index and adding a used[] set so every position can draw from any unused element. Master the choose/explore/un-choose with used-restoration here and Permutations II, N-Queens, and Combinations all reuse the same muscle.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Backtracking for order-matters enumeration (choose → explore → un-choose) with a used[] set and NO start index. Recognise it whenever every arrangement is a distinct answer. The defining contrast with Subsets/Combinations — drop the start index, add used[] — also drives Permutations II and underlies the placement logic in N-Queens.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Permutations IIComing soonInput has duplicates → sort first, then skip `nums[i] == nums[i-1] && !used[i-1]` to avoid duplicate permutations at the same level.
- Next PermutationComing soonOnly the single next ordering in lexicographic sequence → O(n) in-place: find the pivot, swap with the next-larger suffix element, reverse the suffix. No backtracking.
- SubsetsOrder does NOT matter → use a start index instead of used[], and record at every node rather than only full-length leaves.
- CombinationsComing soonChoose k of n where order doesn't matter → start-index template, record when path length == k.