medium
Permutations
Given an array of distinct integers, return all possible orderings of its elements.
Constraints
- 1 ≤ n ≤ 6
- All elements distinct
Examples
in: nums = [1,2,3]
out: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Recognition clues
- n! results — enumeration
- Choose an unused element for each position
- Mark as used, recurse, unmark
Pattern
BacktrackingEnumerating every arrangement is exponential, so tiny bounds plus "all" or "any valid" wording mean search the decision tree: choose, recurse, un-choose. Pruning invalid partial states early (a queen already attacked, a sum already exceeded) is what makes it practical.
Solution
Maintain a current partial permutation and a used-flag per element. At each depth, try every unused element: mark it, append it, recurse, then pop and unmark. When the partial permutation has length n, record a copy. Alternatively swap element i into position depth and swap back after recursing, avoiding the used array.
time O(n · n!)space O(n)
Alternative approaches
- Heap's algorithm generates permutations with one swap each. For lexicographic order, repeatedly apply next-permutation.
Code it yourself
Solve in
Hints: