Permutations
Swap each unused element into the current position, recurse, then swap back.
Recursion & BacktrackingO(n! * n)New4 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
all orderings
anagram generation
assignment with all elements used
The template
Get this into muscle memory, then adapt the condition per problem.
function dfs(i: number) {
if (i === n) { out.push([...a]); return; }
for (let j = i; j < n; j++) {
[a[i], a[j]] = [a[j], a[i]];
dfs(i + 1);
[a[i], a[j]] = [a[j], a[i]];
}
} Watch Permutations (Swap and Recurse)If you are stuck
The generic hint ladder for this pattern, in order.
- 1Fix the first position, then permute the remainder.
- 2Swapping avoids the used array and extra allocation.
- 3Skip a value already tried at this depth to deduplicate.
Drill it
Every problem in the bank that uses this pattern.
0 / 4 solved