46. Permutations
You are given nums, an array of distinct integers. Produce every possible ordering of its elements — with n values there are exactly n! of them — and return the full list.
So the output stays deterministic, return the permutations in ascending lexicographic order: compare two orderings element by element and rank them by the first position where they differ. For [1, 2, 3] that means [1, 2, 3] comes first and [3, 2, 1] comes last.
This is the canonical warm-up for backtracking: choose an element for the current slot, recurse on what remains, then undo the choice.
Example 1:
Input: nums = [1, 2, 3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Explanation: Three distinct values give 3! = 6 orderings, listed smallest-first: everything starting with 1, then 2, then 3.
Example 2:
Input: nums = [0, -1]
Output: [[-1,0], [0,-1]]
Explanation: Two elements give 2 orderings. [-1, 0] sorts before [0, -1] because -1 < 0 at the first position.
Constraints:
- 1 ≤ nums.length ≤ 6
- -10 ≤ nums[i] ≤ 10
- All values in nums are distinct.
Hints:
Build an ordering one slot at a time. At each step, every element you have not placed yet is a valid candidate for the next slot.
Track a boolean `used` flag per index: pick an unused element, mark it, recurse to fill the remaining slots, then unmark it and try the next candidate — that undo step is the heart of backtracking.
Sort nums first and always try candidates from smallest to largest; the permutations then come out already in lexicographic order, no post-sort needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3]
Expected output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]