List every order of a set of numbers. Fill one seat at a time with a number you haven't used, recurse, then take it back and try the next.
▼The problem
LeetCode 46 (Medium). Given an array of distinct integers, return all possible permutations, in any order.
Example: [1, 2, 3] → 6 permutations.
The solution
def permute(nums):
out, path, used = [], [], set()
def go():
if len(path) == len(nums):
out.append(path[:]) # save a copy
return
for x in nums:
if x in used: continue
path.append(x); used.add(x) # choose
go()
path.pop(); used.remove(x) # undo
go()
return outTranscript
Permutations. Given a list of distinct numbers, return every possible order of them.
Take one, two, three. There are six orders: one two three, one three two, two one three, two three one, three one two, and three two one. Three choices for the first seat, two for the second, one for the last: six.
The brute force way fills every seat with any number, then throws out the lists with repeats. That's n to the n lists: twenty-seven, for only six answers.
Instead, fill the seats one at a time. For the next seat, try each number that isn't used yet. Seat it, fill the rest the same way, then take it back out and try the next one. That undo is backtracking.
In code, keep a path and a used set. When the path is full, save a copy. Otherwise, loop over the numbers, skip the used ones, choose one, recurse, then undo the choice.
Let's run it. One, two, three sit down: save one two three. Three gets up, two gets up, three sits, then two: one three two. Back to the first seat. Two goes first, and the same moves give two one three and two three one. Then three goes first: three one two, three two one. Six orders.
There are n factorial orders, and copying each one takes n steps, so the time is n times n factorial. Apart from the output, the path and the used set hold at most n numbers: order n extra space.
Pick a seat, try everyone, step back. That's Permutations.