Intermediate · Module 12 · Lesson 4
Permutations
Track used choices or swap positions.
15–25 min readLesson 67 of 123
Lesson 67 of 123
1d streakTheory lesson · Step-by-step
Understand Permutations
Track used choices or swap positions.
Worked approach
Trace the reasoning step by step
- 1Stop and record when path length equals n.
- 2Try each unused value.
- 3Mark and append it.
- 4Recurse, then unmark and remove it.
Concrete example
Generate permutations of [A,B,C].
- 1Choose A first, then arrange B,C.
- 2Backtrack and choose B, then C first.
There are 3! = 6 leaf arrangements.
What must remain true (Loop Invariant)
The path contains distinct chosen positions; unused choices remain available.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Search tree
Exponential / output-sensitive
O(depth)
Branching factor, depth, pruning, and number of produced answers control cost.When to use it
- Self-similar subproblems, enumeration, constraint solving, and decision trees.
- Generating combinations and permutations.
- Converting overlapping recursion into dynamic programming.
Common mistakes
- Missing a base case or failing to make strict progress.
- Forgetting to undo shared mutable state.
- Using exponential search when states repeat and should be memoized.
Practice prompts
- Reproduce the worked Permutations example without looking at the trace.
- Change one input condition and explain whether the Permutations invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.