1Understand
The idea
Build the ordering position by position: at each step try every element that is not used yet, mark it, recurse, then unmark it. With duplicates in the input, sort first and skip an element that equals the previous one when that previous one is not in use, so each distinct ordering appears once.
Intuition
Build the ordering position by position: at each step try every unused element, mark it, recurse, then unmark. The path length equals n at the leaves.
With duplicates in the input, sort first and skip an element that equals the previous one when that previous one is not used, so each distinct ordering appears once.
Swapping in-place (nums[l] with i) is an equivalent formulation without a separate used array.
What you will be able to do
- Track used elements
- Undo every choice
When to use it
- All orderings / arrangements
- Letter case or phone-keypad combinations
2See it
Walkthrough
Permutations of [1, 2]
Used-mask (or swap) so each value appears once per path.
1 / 6
path []. used=[0,0]. At depth 0 try each unused index.
Live template
Line 1 active
Complexity: time O(n! · n), space O(n)
Time O(n · n!) to generate all permutations. Space O(n). Duplicate-skipping keeps output size equal to the number of unique perms. Sorting + used-flag skip is the standard fix.
Read the walkthrough as text
Permutations of `[1,2,3]`.
- Position 0: try
1, then recurse for positions 1.. with{2,3}left. - Under
1, try2then3→[1,2,3]; backtrack; try3then2→[1,3,2]. - Similarly branches starting with
2and3. Six permutations total.
For [1,1,2], after sorting, when choosing the second 1 while the first 1 is unused, skip, avoids duplicate perms.
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
All permutations
Example. Every ordering of distinct numbers.
How. Track used indices; choose unused at each depth; copy path at full length.
Permutations with duplicates
Example. Unique permutations when nums has repeats.
How. Sort; skip same value at same depth if previous equal unused.
Phone keypad letter combinations
Example. Map digits 23 to all letter pairs.
How. Cartesian backtrack: for each digit, branch over its letters.
Generate valid parentheses
Example. All well-formed strings of n pairs.
How. Track open and close counts; add ( if open<n; add ) if close<open.
Letter case permutations
Example. All case variants of a string with letters and digits fixed.
How. Branch flip case on letters; skip on digits; copy at end.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Choice not undone
Why it happens. Next branch reuses the same path after recursion returns.
How it fails. Forget path.pop() after recurse, path length grows and used set never clears.
Fix. Mirror every choose with unchoose: pop path and remove from used after the call.
Duplicate permutations
Why it happens. Swapping equal values produces different index picks that look like different perms.
How it fails. [1,1,2] emits [1a,1b,2] and [1b,1a,2] as duplicates in output.
Fix. Sort; at each level skip nums[i]==nums[i-1] when i>start and !used[i-1].
Used set by value
Why it happens. Tracking values in a set is simpler than indices.
How it fails. Two 1’s: first 1 in used blocks picking second 1, you miss half the perms or over-prune.
Fix. Track used indices (or visit array by index), not values alone.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.