Permutations
Permutations is LeetCode 46 (Medium). You are given an array nums of distinct integers. Return every permutation of it, that is, every ordering of its elements.
- Order matters: the same numbers in a different order are a different permutation.
- Each permutation uses every element exactly once, none repeated and none left out.
- The permutations may be returned in any order.
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
Intuition
Build each ordering one slot at a time. The first slot can take any of the n values, the second any value except the one already placed, and so on. Every different sequence of choices gives a different ordering, so trying all of them lists each permutation exactly once: n × (n-1) × … × 1 = n! of them.
Backtracking walks those choices depth first:
- Try each open value in the current slot, recurse to fill the next slot, then take the value back out.
The take-back is the whole trick. Every branch shares the same path and used state, so a branch must leave them exactly as it found them, or its next sibling starts from a corrupted state.
Every element must appear and order matters: that is a permutation, and each level of the recursion scans the whole array, skipping what is taken. If order did not matter you would be choosing a subset or combination instead, where a start index moves forward and never looks back.
Approach
Before reading on: for [1, 2, 3], after [1, 2, 3] is recorded, which values do you take back out, and what is the next permutation the search produces? Aim for O(n · n!) time and O(n) extra space.
Grow a path, one slot per level
The recursion depth is the slot being filled, and path holds the values placed so far. When its length reaches n, every slot is full, so path is one finished permutation.
Skip values that are already placed
Keep used[i] for every index and, at each level, loop over all indices, skipping the used ones. Scanning from 0 every time is what lets a later slot hold an earlier element, which is the difference from combinations.
Choose, recurse, un-choose
Set used[i] = True and append nums[i], recurse, then pop it and set used[i] = False. Undoing in reverse order puts both pieces of state back exactly as they were before the next value is tried.
Record a copy at a full path
Append path[:] (Python), new ArrayList<>(path) (Java) or path by value (C++). Backtracking keeps editing the one shared list, so only a copy keeps the finished permutation intact.
The swap method, without a used array
Another way keeps the array itself as the path: for slot k, swap each nums[j] with j ≥ k into position k, recurse on k + 1, then swap back. The open values are always the tail nums[k:], so no used array is needed; it is the same O(n · n!), but harder to follow.
Permutations solution in Python | C++ | Java
Common pitfalls
Carrying a start index over from combinations
def backtrack(start):
for i in range(start, len(nums)):
...
backtrack(i + 1)def backtrack():
for i in range(len(nums)):
if used[i]:
continue
...A start index only moves forward, so a later slot can never hold an earlier element. The search then produces subsets in one fixed order, not orderings. Permutations must be able to reach back, which is why taken values are tracked by a flag, not by position.
Appending the live path
if len(path) == len(nums):
res.append(path)if len(path) == len(nums):
res.append(path[:])res ends up holding the same list object n! times, and backtracking pops it back to empty, so the result is a list of empty lists. Java has the same bug with res.add(path); C++ copies on push_back, so it is safe there.
Complexity
n! permutations and each costs O(n) to copy into the result, which is also the size of the output, so no algorithm can do better. Extra space is O(n) for path, used and the recursion depth, not counting the output.Permutations vs its look-alikes
These four are easy to mix up. The loop start and the dedupe rule are what change.
| Problem | Order matters? | Loop at each level | Extra rule |
|---|---|---|---|
| Permutations (46) | yes | all indices, skip used | none: values are distinct |
| Permutations II (47) | yes | all indices, skip used | sort, and skip nums[i] equal to nums[i-1] when nums[i-1] is not in use |
| Combinations (77) | no | from start forward | stop at k elements |
| Next Permutation (31) | yes | no recursion | one in-place step to the next ordering in dictionary order |
Permutations FAQ
How do you generate all permutations of an array?
- State: a
pathof values placed so far and ausedflag per index. - Leaf: when
pathhasnvalues, record a copy. - Branch: for every unused index, mark it, append its value, recurse, then pop it and unmark it.
- Complexity: O(n · n!) time, O(n) extra space.
- Example:
[1, 2, 3]gives[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].
What is the formula for permutations?
n distinct items can be ordered in n! = n × (n-1) × … × 1 ways: n choices for the first slot, n - 1 for the second, and so on. Ordering only r of them gives n! / (n-r)!. That is exactly the shape of the search: n branches at the top, one fewer at each level down.
How do you get the permutations of a list in Python?
itertools.permutations(nums) yields every ordering as a tuple, so [list(p) for p in permutations(nums)] answers the problem in one line. In an interview you are usually asked to write the permutation algorithm in Python yourself, which is the backtracking above; itertools is fine to mention as the library answer.
Why is Permutations on LeetCode O(n · n!) time?
The search reaches n! full paths, and copying each one into the result is O(n). The partial paths above them add up to less than that, since there are n!/1! + n!/2! + … of them, which is under e · n!. The output alone has n · n! numbers, so this is optimal.