Permutations
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return every ordering (permutation) of a list of distinct numbers.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1How many choices do you have for the first seat, second, third?
- Hint 2Keep a list of who is already seated; when the seating is full, record it and undo.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Seating three guests in three chairs. For the first chair try each guest. For the second chair try each guest who is still standing. For the third, whoever is left. After recording a full seating, take the last person back out and try the next candidate for that chair. That take-back step is the heart of backtracking.
- The obvious way
There are n! answers; any solution must produce them all. Backtracking does this without waste.
- The key insight
A recursive function fills the next seat: loop over all guests; skip those already seated; seat one, recurse for the following seat, then remove them (backtrack). When all seats are filled, save a copy.
- The algorithm
- seating = [], and nobody is marked as seated.
- If every seat is filled, save a copy of the seating.
- Otherwise try each guest not yet seated: seat, recurse, unseat.
- Return all saved seatings.
Watch it run
Examplenums = [1, 2, 3]
Seat 1 first, then 2, then 3: the seating [1,2,3] is full, so record it.
[1,2,3]
Where people slip
- Always undo (pop and unmark) after the recursive call, or later branches see stale state.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def permute(nums):
result = []
seating = []
seated = [False] * len(nums)
def fill_next_chair():
if len(seating) == len(nums):
result.append(list(seating)) # a full seating: save a copy
return
for guest in range(len(nums)):
if seated[guest]:
continue # already in a chair
seated[guest] = True
seating.append(nums[guest])
fill_next_chair()
seating.pop() # backtrack: take the guest back out
seated[guest] = False
fill_next_chair()
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.