Permutations — The Photo Lineup

Boss 3: The Photo Lineup

Bosses 1 and 2 built combinations: what's in the bag, order irrelevant. This boss flips the single assumption, order is the whole answer, and the flip breaks one tool while sparing another. Watching which survives teaches more about backtracking than either boss alone.

The story

The photographer's bench, three friends: 1, 2, 3 (they answer to their jersey numbers). Every left-to-right seating, one photo each:

[1,2,3]  [1,3,2]  [2,1,3]  [2,3,1]  [3,1,2]  [3,2,1]

Six photos, and the count writes itself: seat the leftmost spot (3 choices), then the middle (2 remaining), then the right (1 left). 3 × 2 × 1 = 3! = 6. Factorials grow viciously, 10 friends means 3.6 million photos, so as with subsets, the output is the cost, and the craft is generating each arrangement exactly once with no bookkeeping disasters.

Now the structural break from the last two bosses. In Combination Sum, the no-going-backward floor (start) killed duplicate recipes, because [2,2,3] and [3,2,2] were the same answer. Here [1,2,3] and [3,2,1] are different answers: the floor would forbid seating 1 after 3 and silently delete photos. Index discipline dies. Every not-yet-seated friend is a legal candidate at every seat, whatever their number.

What replaces the floor: the clipboard. A simple used-set, who's already on the bench. The candidates at any seat are exactly the unused friends.

The problem, dressed up properly

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

LeetCode 46.

The naive attempt

Python's itertools.permutations (and its cousins in every language) does this in one line, and in production, use it. The interview wants the machinery. The genuinely naive hand-rolled version: generate all nⁿ sequences of picks and filter out those with repeats, that's 27 candidates for 6 answers at n=3, and the gap explodes factorially. The used-set doesn't filter repeats; it never generates them.

The weapon: seat, arrange the rest, un-seat

The rhythm survives untouched, choose, explore, un-choose, only the candidate list changed:

def permute(nums: list[int]) -> list[list[int]]:
    out = []
    path = []
    used = [False] * len(nums)
 
    def seat():
        if len(path) == len(nums):
            out.append(path[:])              # full bench: snapshot
            return
        for i in range(len(nums)):
            if used[i]:
                continue                     # already on the bench
            used[i] = True                   # choose
            path.append(nums[i])
            seat()                           # explore
            path.pop()                       # un-choose, both halves!
            used[i] = False
    seat()
    return out

Note the un-choose is now two mutations, and both must reverse: the path pop and the used flag. The symmetry law from Boss 1 scales with the state: however many things choose touches, un-choose touches the same ones, in reverse. Half-restored state, the flag cleared but the path not popped, or vice versa, is this dungeon's signature crash-less catastrophe: no error, plausible output, wrong catalog.

Watching it work

nums = [1, 2, 3], tracking bench and clipboard:

seat []: try 1 → [1]
  seat: try 2 → [1,2]
    seat: try 3 → [1,2,3] 📸  un-seat 3
  un-seat 2, try 3 → [1,3]
    seat: try 2 → [1,3,2] 📸  un-seat 2
  un-seat 3
un-seat 1, try 2 → [2]
  ... → [2,1,3] 📸  [2,3,1] 📸
un-seat 2, try 3 → [3]
  ... → [3,1,2] 📸  [3,2,1] 📸

Six photos, and the shape of the tree changed from subsets': that tree was binary and uniform; this one narrows at every level, 3 branches, then 2, then 1. Factorial trees taper. (It's also why the used-check by array beats a hash set here: used[i] is one index, and the loop already iterates indices.)

Gotchas

1. Reusing the combination floor. for i in range(start, ...) deletes every permutation that seats a lower index after a higher one, you'll emit exactly one photo and puzzle over the other five. Order-matters problems track usage, not position.

2. Half un-choose. Popping the path but forgetting used[i] = False (or the reverse). The friend stays phantom-seated forever; later branches see a full clipboard and an unfull bench and produce short, wrong photos. Both mutations, both reversals, adjacent lines.

3. Copy-at-leaf, forever and always. out.append(path) strikes again, six references to one list that ends empty. Boss 1's tattoo (path[:]) applies to every boss in this dungeon; this is its last dedicated mention.

4. Checking nums[i] in path instead of a used flag. Correct for distinct values, and O(n) per check where the flag is O(1), turning O(n·n!) into O(n²·n!). It also collapses the moment duplicates enter (Boss 4's sibling problem, LC 47). The flag tracks the slot, not the value, which is the honest thing being tracked.

Complexity

n! permutations, each copied in O(n).

Time: O(n · n!). Space: O(n) for path, used, and stack.

Boss down. XP gained.

Six prints on the table. They pick [2, 1, 3], the tall one in the middle, obviously, and the photographer bills for six setups anyway.

What you walked away with:

• Order matters ⇒ the index floor dies, replaced by a used-set; the rhythm itself survives everything
• Un-choose reverses all of choose's mutations, symmetric to the letter
• Factorial trees taper: n, then n-1, then n-2 branches, and O(n · n!) is the output's own size
• The swap trick as the O(1)-space encore

Three bosses, all on distinct inputs, and both Boss 1 and this one leaned on that quietly. The next boss breaks the assumption: two identical shirts enter the packing list, and suddenly the subset catalog is full of indistinguishable duplicates. The fix is one sorted array and one carefully aimed skip, the most transferable three lines in the dungeon.

Next up: Boss 4 — The Twin Shirts. Subsets again, but the suitcase holds two identical blue shirts, and [shirt A] versus [shirt B] is a distinction without a difference. Sort, then skip a candidate when it equals its unchosen twin: the dedupe idiom that Bosses 5 reuses verbatim and half of LeetCode's hard filters are built on.