p36 — Permutations

Source: LeetCode 46 · Medium · Topics: Array, Backtracking Companies (2024–2025 frequency): Meta (very high), Google (high), Amazon (high), Microsoft (high), Apple (medium) Loop position: algorithm round opener for backtracking. A weak Permutations attempt signals the candidate hasn’t internalized the technique.

1. Quick Context

Given an array of distinct integers, return all n! permutations. The follow-up (LC 47 — Permutations II, with duplicates) is the staff-level signal.

The canonical pattern is choose / recurse / un-choose with a used[] boolean array:

def backtrack(path):
    if len(path) == n:
        result.append(path[:])      # snapshot
        return
    for i in range(n):
        if used[i]: continue
        used[i] = True; path.append(nums[i])     # choose
        backtrack(path)                          # recurse
        path.pop(); used[i] = False              # un-choose

Time: O(n · n!) (n! permutations × O(n) to copy each). Space: O(n) recursion depth.

The discriminator: a clean used[] template, plus the in-place swap variant (which trades clarity for O(1) less space) and the duplicate-input variant (sort + skip).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/permutations/

STOP. 15-min timer. Write the template from memory.

3. Prerequisite Concepts

• Recursion + stack frames.
• The DFS template (Phase 01 Lab 08).
• Why result.append(path[:]) and not result.append(path) — the list is mutated by un-choose.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “All orderings of n distinct elements. Return as list of lists.”

Step 2 — Clarify:

• “Distinct integers?” (Yes — that’s the constraint that makes used[] sufficient.)
• “Output order matters?” (No — any order accepted.)
• “Constraints on n?” (n ≤ 6 typically. n! grows fast.)
• “Return list or generator?” (List per spec.)

Step 3 — Constraints: n ≤ 6 → 720 permutations. Even at n=10 it’s 3.6M. The constraint is small precisely because the OUTPUT is exponential.

Step 4 — Examples:

• [1,2,3] → 6 permutations.
• [1] → [[1]].
• [] → [[]] (the empty permutation; verify with interviewer).

Step 5 — Brute Force: Iterative generation via itertools.permutations. State, then write the manual backtracking — the interviewer wants the recursion.

Step 6 — Complexity: O(n · n!) time (n! results, O(n) copy). O(n) recursion + O(n) used[]. Output is O(n · n!).

Step 7 — Pattern: “Enumerate all X” → backtracking. The shape of X (permutation/combination/subset) picks the template:

• Permutation: used[] array, all elements at each level.
• Combination: start index, monotonically non-decreasing.
• Subset: include/exclude OR start-index variant.

Step 8 — Develop: see solution.py. Both used[] and swap-in-place variants.

Step 9 — Test: edge cases (empty, single, duplicates-in-input-shouldnt-happen-but-verify). Stress vs itertools.permutations.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Three permutation algorithms

6.1 used[]-array backtracking (the default)

Pros: clearest code; matches the universal backtracking template; trivially extends to LC 47 (duplicates) via sort + skip-if-duplicate-sibling.

Cons: O(n) extra space for the used[] array.

6.2 Swap-in-place (Heap’s-algorithm-style)

def backtrack(start):
    if start == n:
        result.append(nums[:])
        return
    for i in range(start, n):
        nums[start], nums[i] = nums[i], nums[start]   # choose: bring i to position start
        backtrack(start + 1)
        nums[start], nums[i] = nums[i], nums[start]   # un-choose: swap back

Pros: no used[] array. Mutates input but restores it.

Cons: produces permutations in a different (non-lexicographic) order. Less obvious correctness. Cannot be adapted to LC 47 (duplicates) without explicit duplicate tracking — the swap technique loses the “we’ve already tried this value at this position” information.

6.3 Iterative (Heap’s algorithm proper)

Generates the next permutation by a clever swap-and-reverse sequence. O(1) extra space, O(n!) iterations. Beautiful but rarely needed in interviews — mention it only if asked about generating permutations on a memory budget.

6.4 LC 47 — duplicates (THE follow-up)

Sort the input. In the loop, skip a value if its previous-equal sibling is not currently used:

for i in range(n):
    if used[i]: continue
    if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue
    ...

Why not used[i-1]? Because when used[i-1] IS true, we’re inside a subtree where nums[i-1] was already placed earlier in the path — so nums[i] is now a legitimate next choice. When used[i-1] is FALSE, we’ve returned from that subtree (un-chose it), and choosing the equal-value nums[i] next would regenerate the same permutation.

This is the single hardest line in backtracking. Memorize it.

6.5 Why pure deduplication-via-set is wrong

A common bad pattern: generate all n! permutations (with duplicates), then set(tuple(p) for p in result). This is exponential WORK for what should be linear-in-output. With n=8 and many duplicates, the set approach generates 40320 permutations to find ~100 unique ones — 400× wasted work. The interviewer notices.

7. Anti-Pattern Analysis

1. result.append(path) instead of path[:]. Result: all entries point to the same mutated list → after the recursion ends, every entry is [].
2. Building a new list per recursion (backtrack(path + [nums[i]])). Works but allocates a fresh O(n) list per node — n! nodes × n = O(n² · n!) work. The append/pop pattern is O(n · n!).
3. used = [False] * n inside the recursion. Resets state on every call — produces wildly wrong output. used must be hoisted to the closure.
4. Forgetting the pop(). Path grows monotonically; first result is the only correct one.
5. set() dedup at the end for LC 47. Exponentially wasteful (see 6.5).
6. Using a string for path. path = path + ch is O(L) copy per call; use a list.
7. Validating “is this a permutation” at the leaf. Pruning happens AT THE CHOICE, not at the result.
8. Outputting tuples instead of lists. Off-spec for LC; trivially wrong on grader.

8. Skills & Takeaways

• The universal choose / recurse / un-choose template — write it from muscle memory.
• used[] for permutations; start index for combinations/subsets.
• result.append(path[:]) to snapshot mutable state.
• Duplicate-input dedup line: if i > 0 and a[i] == a[i-1] and not used[i-1]: continue.
• The 3 variants and their trade-offs.
• Why backtracking time is O(branching^depth × leaf-work).

9. When to Move On

Move on when:

• You can write the used[] template in under 90 seconds.
• You can write the swap variant in under 2 minutes.
• You can write LC 47 (duplicates) in under 5 minutes.
• Your stress test of 300 random inputs (n=1..5) matches itertools.permutations.

10. Company Context

Meta:

• One of the canonical Meta backtracking warm-ups. The interviewer expects clean code and immediate transition to LC 47.
• Scorecard phrase: “Algorithm — clean backtracking template, articulated the dedup rule.”

Google:

• Common L4/L5 opener. Often paired with “now constrain by some predicate” (e.g., “only valid IP-address-like permutations”).
• Scorecard phrase: “Strong — wrote template confidently; pruned at choice not leaf.”

Amazon:

• L5 phone screen staple. Bar Raisers care about correctness + complexity discussion + handling of edges.
• Scorecard phrase: “Strong — handled duplicates with sort+skip; explained the not used[i-1] line.”

Microsoft:

• L63 standard. Often combined with “now print them in lex order” — gives you the sort up front.

Apple:

• Appears in algo rounds especially for media teams (audio sequencing, animation timing).

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• used[] template, correct snapshot, n=1 and n=3 work.

Senior (L5):

• Both used[] and swap-in-place.
• Solves LC 47 with correct dedup.
• Discusses O(n · n!) time and O(n) extra space.

Staff (L6):

• All three (used, swap, Heap’s next-permutation iterative).
• Discusses generator-based variants for memory-bounded environments.
• Recognizes when permutation enumeration is the wrong tool — e.g., k-th permutation (LC 60) via factorial-number-system, NOT enumeration.

Principal (L7+):

• Discusses production: permutation enumeration appears in cryptographic test fixtures, brute-force key-search tools (rare), constraint solvers (CSP backtracking), and combinatorial test generation.
• Discusses parallel backtracking: distribute subtrees across workers; load-balancing via work-stealing.
• Discusses probabilistic vs exhaustive search: when n is too large, switch to Monte Carlo / simulated annealing / genetic algorithms.

13. Follow-up Q&A

Q1: K-th permutation (LC 60). A: Don’t enumerate. Use the factorial number system: the i-th element of the k-th permutation is determined by k // (n-1-i)! after each step. O(n²) (or O(n) with linked-list deletion). NEVER backtrack to find the k-th.

Q2: Permutations with duplicates (LC 47). A: Sort + if i > 0 and a[i] == a[i-1] and not used[i-1]: continue. The not used[i-1] ensures we only pick the FIRST equal value at any given depth — canonical-form pruning.

Q3: Generate permutations one at a time (iterator). A: Python generator with yield. Iterative version: Heap’s algorithm or next-permutation (LC 31). O(1) amortized per generation.

Q4: Permutations of size k (partial permutations) — P(n, k). A: Same template, exit when len(path) == k instead of n. Or use combinations + permutations (C(n, k) * k!).

Q5: Distributed permutation enumeration. A: Each worker takes a fixed prefix (e.g., first 2 elements), generates suffixes locally. Static partition is easy; work-stealing fixes load imbalance.

14. Solution Walkthrough

See solution.py:

• permute(nums) — used[] backtracking. Default.
• permute_swap(nums) — swap-in-place variant. Mutates and restores input.
• permute_unique(nums) — LC 47 with sort + skip-dedup.
• permute_brute(nums) — itertools.permutations oracle.
• edge_cases() + stress_test() — verify all three vs the oracle.

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“Three things. (1) The path[:] snapshot is THE bug source for everyone new to backtracking — write a one-line comment explaining why. (2) For LC 47, the not used[i-1] is non-obvious; add a worked example in the comments showing how [1,1,2] produces [[1,1,2],[1,2,1],[2,1,1]] (3 perms) instead of 6. (3) If this code goes into a library, expose a GENERATOR variant — for n=10 the result list is 3.6M items × ~80 bytes = 280MB. A generator lets the caller consume on the fly. Same template, replace result.append(...) with yield list(path).”

Connections forward:

• p37 — Combinations: same template, different choice rule (start index).
• p38 — Subsets: same template, two-way choice (include/exclude).
• p40 — N-Queens: backtracking with stateful attacker sets.
• LC 31 — Next Permutation: iterative O(n) alternative.
• LC 60 — Permutation Sequence: factorial number system.
• LC 47 — Permutations II: the duplicate variant (THE staff signal).
• Phase 02 Lab 08 — Backtracking: full pattern lab.
• Production: constraint solvers (CSP), combinatorial test generation, branch-and-bound.