Every ordering of the items
List all the orderings of distinct numbers by choosing the next unused number at each position, recursing, and marking it unused again when you come back. About 16 minutes.
Fill one position at a time
An ordering of n items has n positions. Fill them from left to right. For the first position, any of the n items can go. For the second, any item that is not already used. And so on.
Keep a flag for each item saying whether it is already placed. Loop over the items; skip the placed ones; place a free one, and move on to the next position.
used = [False] * n used[i] = True # take it used[i] = False # give it back
Choose 2 first. Then 4 then 7, then 7 then 4 for the rest: 2,4,7 and 2,7,4.
Undo on the way back
After the call for the next position returns, the item you placed must be made free again, so that the next iteration of the loop can use it elsewhere. That is the undo step of backtracking.
The current ordering is one list that is overwritten as you go, so when you find a complete one, save a copy, not the list itself. The answers come out in order: those that start with the first item, then the second, and so on.
cur.append(nums[i]) go(depth + 1) cur.pop()
Why is the used flag set back to false after the recursive call?
- ASo the item can be placed in another position in the next iteration
- BTo make the code faster
- CTo copy the list
Show the answer
So the item can be placed in another position in the next iteration. Each iteration starts with the same set of free items.
Permutations
Given an array nums of distinct integers, return all the possible orderings (permutations) of its values. List them in the order that results from choosing, at each position, the unused values in the order they appear in nums.
nums = [1, 2, 3] → [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
1 ≤ length of nums ≤ 6 · -10 ≤ nums[i] ≤ 10 · all values are different