LeetCode 46 ·
Medium
Permutations
Return all permutations of an array of distinct integers.
Try it
Step through the core mechanic. The simulator below runs the backtracking shape this problem is built on.
Interactive · Recursion call tree — Fibonacci naive recomputes; memoised short-circuits on cache hits
Mode O(2ⁿ) calls
enter fib(6)
total calls1 unique values≤ 7 modenaive
Toggle the modes.
Naive at n=6 makes 25 calls. Memoised at n=6 makes 11 calls — and the cache
hits (amber circles) are the difference. The shape of the tree changes
dramatically: naive is a fat exponential tree; memoised collapses to a
near-linear path with stub returns where the cache hits.
The approach
Backtrack with a used[] flag (or in-place swaps). At each depth pick an unused element, recurse, then undo the choice. n! leaves, each a complete permutation.
| Aspect | Value |
|---|---|
| Pattern | Backtracking |
| Recognise it by | All orderings of distinct elements. |
| Time complexity | O(n·n!) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.