Permutations
Problem statement
You're given an array of distinct integers, nums. Return every possible
ordering (permutation) of nums, in any order.
Think of it as every possible order to run a handful of independent setup scripts or config changes, when you need to check whether the order actually matters.
Examples
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 have 3! = 6 possible orderings, and all six are listed.
Example 2
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Explanation: Two values have 2! = 2 possible orderings.
Example 3
Input: nums = [1]
Output: [[1]]
Explanation: A single value has exactly 1! = 1 possible ordering — itself.
Hints
Approach
Optimal: In-place swapping
Intuition
Instead of tracking which values have been used with a separate array,
permute nums in place. At recursion depth start, everything before
start is already fixed in its final position, and everything from
start onward is exactly "what's still available." Try placing each
remaining candidate into position start by swapping it there, recurse to
fix the next position, then swap back to undo that choice before trying
the next candidate. Once start reaches the end of the array, every
position is fixed — record a copy of nums as one completed permutation.
Steps
- Define a recursive helper taking a
startindex. - Base case: if
startequalsn, append a copy ofnumsto the result and return. - Recursive case: for each index
ifromstartton - 1: swapnums[start]andnums[i], recurse withstart + 1, then swap them back before trying the nexti. - Call the helper with
start = 0, then return the result.
Dry run
nums = [1, 2, 3] — tracing the i = 0 and i = 1 branches at the
deepest levels fully; the i = 1 and i = 2 branches at start = 0
follow the identical swap → recurse → swap-back pattern to produce the
remaining four permutations:
| start | i | swap | array after | action |
|---|---|---|---|---|
| 0 | 0 | (0,0), no-op | [1,2,3] | recurse to start=1 |
| 1 | 1 | (1,1), no-op | [1,2,3] | recurse to start=2 |
| 2 | 2 | (2,2), no-op | [1,2,3] | start=3 (end) → record [1,2,3] |
| 1 | 2 | (1,2) | [1,3,2] | start=2 (end) → record [1,3,2], then swap back to [1,2,3] |
After both branches under start=1 finish, the array is restored to
[1,2,3], and start=0 moves on to i=1 (swap (0,1) → [2,1,3]) and
i=2 (swap (0,2) → [3,2,1]), each producing two more permutations the
same way. All 6 permutations from Example 1 are produced exactly once,
though not necessarily in that example's exact order.
Edge cases: nums with one element hits the base case almost immediately
(start = 0, i = 0 swaps with itself, then start = 1 = n), matching
Example 3.
Complexity
Time O(n! · n) - the same bound as the other two approaches; there's no way to avoid producing n! permutations, each costing O(n) to copy into the result.
Space O(1) - extra beyond the recursion stack and the output — no `used` array and no per-step list of partial permutations are needed at all, since `nums` itself is reused and restored via swaps.
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result: List[List[int]] = []
def backtrack(start: int) -> None:
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start] # swap back
backtrack(0)
return result
if __name__ == "__main__":
print(Solution().permute([1, 2, 3])) # 6 permutations, order may vary
print(Solution().permute([0, 1])) # order may vary
print(Solution().permute([1])) # [[1]]RecapThe whole problem in a few lines, for the night before
- Spot it: "generate every possible ordering of a small set" — permutations, n! growth
- Idea: fix one position at a time and try every not-yet-used candidate there, either with a
usedarray or in place via swapping; or build permutations of longer prefixes by inserting the next element into every gap of every shorter permutation - Cost: O(n! · n) time and space for every approach — n! permutations, each up to length n
- Trap: forgetting to swap back (or unmark used) before trying the next candidate corrupts every later branch — the same backtracking discipline as Subsets, just with a used-tracking or swap-restore step instead of an include/exclude toggle
Interview follow-ups
What if
numscould contain duplicates, and the result shouldn't contain duplicate permutations (Permutations II)?Sort
numsfirst. In the used-array backtracking approach, skip trying a candidate at a given recursion depth if it equals the previous candidate at that same depth and the previous one hasn't been used yet on the current path (aused[i-1] == falseguard). This avoids generating the same permutation twice while still correctly using every duplicate value the right number of times.How would you produce just the kth permutation in lexicographic order, without generating all of them first?
There's a direct construction based on factorials: since there are
(n-1)!permutations starting with any fixed first element, the first element can be picked directly by dividingkby(n-1)!, and the same idea then repeats on the remainingn-1elements. This answers "what's the kth permutation" in O(n²) time without ever generating the othern! - 1permutations.
Frequently asked questions
Because the swap-based approach re-purposes nums itself as the bookkeeping: everything before start is already fixed in place, and everything from start onward is exactly "what's still available" to place next. There's no need for a separate structure to track which values have been used, since the array's own layout already encodes it.
No. Every swap made going deeper into the recursion is undone by an identical swap coming back out (the "swap back" line), so by the time the outermost call returns, nums is back in its original order. It's only ever mutated temporarily, during the recursion itself.
Because there are n! permutations total, and writing out each one costs up to O(n). Producing the full answer requires at least that much work no matter the method — whether that work is spent copying a path, inserting into every gap, or copying the array after a sequence of swaps.
Trying every possible ordering of a small set of steps — the order to run n independent setup scripts, the order to apply n config changes when order might matter, the order to check n conditions — is exactly enumerating permutations. It's only realistic to brute-force while n stays small, which is why this problem caps nums at 6 elements: 6! is 720, while 10! is already over 3.6 million.