Permutations
On this page
Problem statement
Given a list of distinct integers, return every possible ordering of them. The orderings can be returned in any order. With n numbers there are n! of them, so n is small (at most about 8).
This is the textbook backtracking problem. Once you can write it cleanly, Subsets, Combination Sum and N-Queens are small changes to the same template. Original problem: LeetCode 46.
Example

Input: [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Input: [0, 1]
Output: [[0,1], [1,0]]
Constraints (assumed)
- 1 ≤ n ≤ 8.
- All numbers are distinct, −10 ≤ value ≤ 10.
What this question tests
- Writing the choose → recurse → un-choose backtracking template without mistakes.
- Knowing what state to keep (the path and which numbers are used) and how to restore it.
- Reasoning about output-sized complexity: you can't beat n! when you must print n! answers.
Questions to ask first
- Are the numbers distinct? If not, duplicates need extra handling (see Variants).
- Does the output order matter? (Here: no.)
- How large is n? n! grows fast: 10! is already 3.6 million lists.
- Do you want all of them, or just the next one / the k-th one? Those are different problems with better answers.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.