Permutations
Generate every permutation of distinct numbers with backtracking: choose an unused number, recurse, then un-choose it so the next branch starts clean.
Problem Understanding
Permutations: given an array nums of distinct integers, return all possible orderings of them, in any order.
Example: nums = [1, 2, 3] returns [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]], which is 3! = 6 permutations.
The Intuition: Fill Slots, Then Undo
A permutation is n slots filled one at a time. Slot 1 can be any of n numbers, slot 2 any of the remaining n − 1, and so on. That decision tree is exactly what backtracking explores:
- Choose: pick a number that is not used yet, mark it, append it.
- Explore: recurse to fill the next slot.
- Un-choose: pop it and clear the mark, so the next choice at this level starts from the same state.
When the path is full, record a copy. Compare Subsets, where order does not matter and each level only looks forward, and Combination Sum, which adds a target.
Interactive Walkthrough
The numbers are on top, with used ones tinted; the path being built is below. Each step either chooses a number, records a full path, or backs out of a choice. Finished permutations collect beside the figure. Try Four numbers to watch all 24 appear.
Dry Run Table
Input: nums = [1, 2, 3]
| Path | Action |
|---|---|
| [1] | choose 1 |
| [1, 2] | choose 2 |
| [1, 2, 3] | choose 3, record |
| [1, 2] → [1] | undo 3, undo 2 |
| [1, 3] | choose 3 |
| [1, 3, 2] | choose 2, record |
| [] | undo back to the root |
| [2] … | repeat with 2 first, then 3 first |
Answer: 6 permutations.
The Solution Template
The choose / explore / un-choose template with a used array. In C the result has n! rows, so it is sized up front.
Permutations Code
1var permute = function(nums) {2 const res = [], path = [], used = new Array(nums.length).fill(false);3 const backtrack = () => {4 if (path.length === nums.length) {5 res.push([...path]);6 return;7 }8 for (let i = 0; i < nums.length; i++) {9 if (used[i]) continue;10 used[i] = true;11 path.push(nums[i]);12 backtrack();13 path.pop();14 used[i] = false;15 }16 };17 backtrack();18 return res;19};
Edge Cases & Common Mistakes
- Appending the path itself:
res.append(path)stores a reference that later pops empty; append a copy. - Forgetting to un-choose: if
used[i]is not reset after the recursive call, later branches skip numbers they should try. - One number: the only permutation is
[nums[0]]. - Duplicates in the input: this template would repeat permutations; Permutations II sorts the input and skips a number equal to its unused left neighbour.
- Swap-based alternative: swapping
nums[start]with each later index avoids the used array but produces a different order.
Summary
Fill the permutation slot by slot. At each level, for every unused number: mark it, append it, recurse, then pop and unmark it. Record a copy whenever the path is full. O(n · n!) time and O(n) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet