Permutations
Why it exists
Problem: We need to generate all possible ordered arrangements of a distinct set of elements (n-factorial sequences).
Naive approach: Randomly shuffling the array and storing unique results in a set, which is highly inefficient and non-deterministic.
Better idea: Build the arrangement position by position. At each position, choose any element that hasn't been used yet. Use a boolean array `used[]` to track availability.
Mental model
Filling chairs on a stage. For the first chair, you can pick any of the n actors. For the second chair, you can pick any of the remaining n-1 actors.
The decision tree branches on 'which unused element goes in the current position'. The branching factor shrinks by 1 at each level: n branches, then n-1, down to 1. This creates exactly n! leaves.
Repeated decision: For the current position in the sequence, which currently unused element should I place here?
Explanation
Permutations differ from subsets because order matters: `[1, 2]` is different from `[2, 1]`. Therefore, we cannot just move a `start_index` forward.
Instead, at EVERY recursive step, we must consider the entire array. To prevent reusing the same element twice in a single permutation, we maintain a `used[]` boolean array.
Hand-trace for `[1, 2, 3]` at depth 0 (first position):
- Choose 1 (mark used). Recurse to depth 1 (second position).
- Choose 2 (mark used). Recurse to depth 2 (third position).
- Choose 3. Path is `[1, 2, 3]`. Record and backtrack.
- Un-choose 2.
- Choose 3 (mark used). Path is `[1, 3]`. Recurse to depth 2.
- Choose 2. Path is `[1, 3, 2]`. Record and backtrack.
- Un-choose 1.
- Choose 2... and so on.
The time complexity is O(n * n!) because there are n! permutations, and copying each to the results takes O(n).
An alternative space optimization exists (Heap's Algorithm or swap-in-place), which swaps elements in the array to avoid the `used[]` array, but the boolean array tracker is the standard interview approach because it's easier to read and extend.
Key points
- Subsets vs Permutations: Subsets = decision per element, 2^n leaves, no tracker needed. Permutations = decision per position, n! leaves, tracker needed.
Pattern: Exhaustive Arrangement
Recognition cues:
- All permutations
- Ordered arrangements
- Factorial time complexity implied (n <= 10)
Engineering examples
Brute-force scheduling
Evaluating all possible execution orders for a small set of interdependent tasks.
Generates all n! task permutations to simulate and score.
Common mistakes
- Forgetting to unmark the used tracker: If you don't set `used[i] = false` after the recursive call, sibling branches will think the element is still taken, silently pruning valid paths and missing most permutations.
Recall questions
- How does the permutation decision tree differ from the subset decision tree?
- Why do permutations require a `used[]` array but subsets do not?
- What is the time complexity of generating permutations?
Questions & answers
Given an array of distinct integers, return all the possible permutations.
Use backtracking with a `used` array. Loop from 0 to n-1. If `used[i]` is false: choose it, set `used[i] = true`, recurse, then un-choose by setting `used[i] = false` and popping.
Approach: Standard permutations template with an availability tracker.
How can you optimize permutation generation to O(1) auxiliary space?
By swapping elements in-place instead of using a `path` and a `used` array. At depth `i`, swap `nums[i]` with every element from index `i` to `n-1`, recurse, and swap back.
Approach: In-place swapping avoids external trackers.
Continue learning
Previous: Backtracking template