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.
Think of this like arranging 3 specific books on a shelf. You must use all 3 books, and putting them in the order A-B-C is a completely different arrangement than C-B-A. Because every book must be used exactly once per arrangement, we can't just move forward blindly—we need to be able to pick any book that hasn't been placed on the shelf yet, regardless of where it started in the pile.
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.
(1) result collects the finished orderings, and path is the ordering being built.
(2) used[i] says whether element i is already in path. A permutation uses every element exactly once, so we must know which ones are taken.
(3) backtrack() fills the next position of path. It needs no arguments, because path and used hold everything.
(4) path is full, so it is one complete ordering. Save a copy and stop.
(5) Try every element for the next position, starting from 0 each time. Unlike subsets, order matters here: [1, 2] and [2, 1] are different permutations, so we must be allowed to look back at earlier elements.
(6) Skip elements already placed.
(7) Mark this element as used, and
(8) place it in the next position.
(9) Fill the remaining positions.
(10) Undo the placement, and
(11) mark the element as free again, so the next choice at this position starts from a clean state.
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.
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 result
It 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.
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 continue
Read 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 produce duplicates or lose valid answers. Trace [1,1,2] by hand once to see it.
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.
Let's break this down:
Time Complexity: There are n! permutations (for the first spot you have n choices, for the second n-1, etc.). For each of these n! valid permutations (leaves of the tree), we make a full copy of the path array of length n. Thus, creating all copies takes O(n \cdot n!) time. The number of internal nodes in the tree is less than n!, so leaf copying dominates.
Space Complexity: The recursive call stack goes exactly n levels deep. The path and used arrays also take O(n) space. So auxiliary space is strictly O(n).
Next Permutation (LeetCode 31) — a completely different problem despite the name. It finds the single next permutation in dictionary order in O(n), with no recursion at all. Find the rightmost place where the numbers go up, swap it with the smallest larger value to its right, then reverse everything after it. A generator like itertools.permutations can produce orderings one at a time using a step much like this.
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.
"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.