Appearance
4.18.3 — Permutations
LeetCode 46 · Medium · ★ Blind 75
The problem
Return every ordering of the array. All values are distinct.
[1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]n is at most 6, so at most 6! = 720 results.
The pattern
This is the third loop shape, and the difference from combinations is one sentence:
Order matters, so
[1,2]and[2,1]are both answers.
That kills the start index. In 4.18.1 and 4.18.2, the loop ran from start forwards precisely to stop both orderings being generated. Here you want both, so the loop runs over everything — and you need a different way to avoid using the same element twice within one permutation.
That way is a used-marker.
The tree:
[]
/ | \
[1] [2] [3] 3 choices
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2] 2 choices each
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] 1 choice each3 \times 2 \times 1 = 6 leaves. Only the leaves are answers, unlike subsets where every node was one.
The solution
python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums): # only full-length paths count
result.append(path[:])
return
for i in range(len(nums)): # every element, every time
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack()
path.pop() # undo both
used[i] = False
backtrack()
return resultts
function permute(nums: number[]): number[][] {
const result: number[][] = [];
const path: number[] = [];
const used = new Array(nums.length).fill(false);
function backtrack(): void {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
backtrack();
path.pop();
used[i] = false;
}
}
backtrack();
return result;
}Two pieces of state, so two undos. path.pop() and used[i] = False must both happen. Forgetting the second is the classic bug here: elements stay marked as used and later branches find nothing available, so the output is short and mysteriously missing entries.
The base case checks length, not an index. A permutation is only complete when every element has been placed.
No start index anywhere. If you find yourself writing one in a permutation problem, you have the wrong shape.
The swap version
There is a neater-looking alternative that needs no used array. Swap the current position with each candidate, recurse, then swap back.
python
def permute(self, nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # choose
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start] # undo
backtrack(0)
return resultIt uses O(1) extra space beyond the output, since the array itself carries the state.
The catch: it does not produce the permutations in lexicographic order, and it becomes awkward when the input has duplicates, because the sorted-order needed for the duplicate skip is destroyed by the swaps. The used array version handles duplicates cleanly.
Prefer the used version. Mention the swap version as an alternative and say why you did not pick it.
Duplicates: Permutations II
LeetCode 47 allows repeated values, and asks for unique permutations only. Two changes:
python
nums.sort() # 1
...
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: # 2
continueRead the second condition carefully, because it is the subtlest guard in the whole chapter.
not used[i-1] means the previous equal value has not been placed on this path. If it has not been placed, then choosing this copy now would produce exactly the arrangement that the earlier copy will produce when its turn comes — a duplicate among siblings.
If the previous copy has been placed, then this copy is legitimately the second one in the permutation, and it must be allowed.
Sorting first is what makes equal values adjacent so that nums[i] == nums[i-1] finds them.
Get this wrong in either direction and you either emit duplicates or lose valid answers. It is worth tracing [1,1,2] by hand once.
Complexity
O(n! \times n) time — n! permutations, each costing O(n) to copy.
O(n) space for the recursion, the path and the used array.
The factorial is unavoidable: the output has n! entries.
Where this goes next
- Permutations II — above.
- Next Permutation (LeetCode 31) — a completely different problem despite the name. It finds the single next permutation in lexicographic order in O(n), with no recursion at all: find the rightmost ascent, swap it with the smallest larger value to its right, then reverse the suffix. Worth knowing, because it is what
itertools.permutationsdoes internally to iterate lazily. - Letter Combinations of a Phone Number — a permutation-shaped problem where the choices at each position come from a lookup table. 4.18.8.
- N-Queens — a permutation of column positions, with extra constraints. 4.18.9.
What the interviewer will push on
"Why no start index?" Order matters, so both [1,2] and [2,1] are wanted. A start index exists to suppress one of them.
"How many permutations are there?" n!, and say it before coding.
"You have two pieces of state — did you undo both?" Yes. This is asked because it is the common bug.
"What changes with duplicate values?" Sort, then the not used[i-1] guard, and be ready to explain what it means.
"Can you avoid the used array?" The swap version, at the cost of ordering and duplicate handling.
One thing to volunteer: state which of the three shapes you are using and why, in one sentence. "Order matters here, so it is the used-marker shape rather than the start-index shape."
Next: 4.18.4 Subsets II — the duplicate-skip rule in its cleanest form.