parikshan

permutations

Difficulty: Medium  ·  Topic: Backtracking  ·  Practice it on parikshan: /practice/permutations/start

The story

You run logistics for an Amazon delivery hub. A driver has eight stops to make today. Dispatch wants to know: of all possible visit orders, which keeps the truck closest to the depot at every step, and which is the worst case? The route optimiser does not have a built-in answer; it wants you to enumerate every permutation of the eight stops, run a scoring function on each, and return the best and worst.

That is permutations. The pattern recurs everywhere a small fixed set of items must be tried in every possible order: which order to apply migrations, which order to ask validation questions in a UX flow, which order to evaluate predicates in a query optimiser. Once n grows beyond ~10 the factorial explodes and you reach for branch-and-bound or DP-with-bitmask. Up to n = 10, brute permutation enumeration is the right tool and you should be able to write it without thinking.

What's actually being asked

Given an array of n distinct integers, output every permutation. There are exactly n! of them. Print them in lex order: compare element by element, smaller first.

The naive approach

Three contenders, all enumerate n! permutations:

  1. Backtracking with a used set. Build position by position; for each empty slot, try every unused value, recurse, undo.
  2. Heap's algorithm. Generate each permutation by a single swap. Beautifully terse; does not produce lex order.
  3. next_permutation. Start from the sorted array, repeatedly compute the lexicographic next permutation in O(n). Produces lex order in O(1) extra memory.

The used-array backtracking is the one that maps cleanly to the canonical skeleton and that you should reach for first. The other two are alternatives to know but not the daily driver.

The canonical backtracking skeleton

def backtrack(state):
    if is_solution(state):
        record(state)
        return
    for choice in choices(state):
        apply(state, choice)
        backtrack(state)
        undo(state, choice)

For permutations:

  • state: (path, used) where path is the prefix and used[i] is True if nums[i] is already placed.
  • is_solution: len(path) == n.
  • choices: every index i where used[i] is False.
  • apply: used[i] = True; path.append(nums[i]).
  • undo: path.pop(); used[i] = False.
  • prune: implicit, used[i] skips already-placed values, that is the entire constraint.

Compare with subsets: there, the state was (path, start) and we monotonically advanced. Here we revisit indices but block already-used ones. The shape of the recursion is identical; only the state and the choice filter differ.

The key insight

What makes permutations different from subsets is that every position can use any of the unplaced values. So we cannot use a monotone start index; we need a membership filter. The cheapest one is a boolean array the same length as nums. Generated code sometimes uses a Python set of values, which is fine when values are hashable but slower and slightly more bug-prone (the set must be of values, not indices, and that asymmetry trips agents).

To get lex order for free, sort nums ascending and always iterate indices 0, 1, ..., n - 1 in order. The first finished permutation is nums itself (smallest); the last is its reverse (largest). Every intermediate permutation comes out in lex order, same iteration order as itertools.permutations(sorted(nums)).

Step-by-step approach

  1. Sort nums ascending.
  2. Allocate used = [False] * n and path = [].
  3. Define dfs(). Base: if len(path) == n, append list(path) to the output and return.
  4. Loop i from 0 to n - 1: if used[i], skip; else set used[i] = True, push nums[i], recurse, pop, set used[i] = False.
  5. Call dfs(). Print n!, then every recorded permutation.

Worked example

nums = [1, 2, 3]

The DFS unfolds:

  • Pick 1 → pick 2 → pick 3 → record [1, 2, 3].
  • Backtrack to depth 2, pick 3 → pick 2 → record [1, 3, 2].
  • Backtrack to depth 1, pick 2 → pick 1 → pick 3 → record [2, 1, 3].
  • And so on, in lex order, until [3, 2, 1].

Six permutations, exactly 3! = 6, in lex order. Match against the expected output.

The swap-based alternative

Instead of a used array, you can swap in place:

def dfs(start):
    if start == n:
        out.append(list(nums)); return
    for i in range(start, n):
        nums[start], nums[i] = nums[i], nums[start]
        dfs(start + 1)
        nums[start], nums[i] = nums[i], nums[start]

This is the constant-extra-memory variant. It does not produce lex order, the swap at position 0 with index i puts nums[i] at the front, breaking the ascending sweep, so you would sort the result if the spec demands it. Use this when you do not need lex order and you want to save n booleans, e.g. on a memory-tight embedded device or in a tight inner loop generating millions of permutations to stress-test a scheduler.

itertools.permutations(sorted(nums)) in Python is the production answer when the spec allows it: it is a C-level generator and emits in lex order directly. The DFS skeleton is what you write when the interview, or the spec, asks you to demonstrate the pattern.

Complexity

  • Time: O(n * n!). The n! permutations each take O(n) to materialise and copy out.
  • Space: O(n) for the recursion stack plus used array; O(n * n!) for the output.

This is optimal: the output itself is Theta(n * n!) integers.

Common pitfalls

  • Appending by reference: out.append(path) instead of out.append(list(path)). Every recorded permutation ends up identical (the final state of path). Same bug as in subsets, same fix.
  • Symmetric undo: every used[i] = True must have a matching used[i] = False. Off-by-one here is the second most common bug.
  • Wrong filter: skipping used[i] with continue is right; using if i in used where used is supposed to be a boolean array is wrong (in on a list of bools is unrelated to membership).
  • Trying to deduplicate after the fact: not needed if inputs are distinct; the permutations-ii variant deals with duplicates and needs a different prune.

Where this shows up in the enterprise

  • Amazon / FedEx route planning: enumerate small TSP instances exactly; the result feeds branch-and-bound for larger ones.
  • Adobe Premiere / Final Cut Pro: try every order of effects in a render pipeline to find the lowest-latency composition.
  • Snowflake / BigQuery query optimisers: enumerate join orders for small n; switch to DP for large n.
  • Pharma scheduling: every order of drug administration for a phase-1 study where order matters.
  • Robotics task planning: every order of pick-and-place operations a six-axis arm could try on a small batch.
  • Hashicorp Terraform: every order of resource creation when dependencies are ambiguous (deliberately rare, but the test suite covers it).
  • Sports tournaments: every fixture order for a round-robin pool when scheduling broadcasters.

If n > 10, the answer is usually "you don't actually enumerate; you DP". traveling-salesman-bitmask-dp solves the same shape in O(n^2 * 2^n) rather than O(n!), a huge win at n = 15 and beyond.

Variants you'll see elsewhere

  • permutations-ii: duplicates allowed. Sort, then when iterating, skip nums[i] == nums[i-1] && !used[i-1]. The trick is subtle: skipping based on used[i-1] being false ensures duplicates only occur in the canonical order.
  • next-permutation: compute the lex-next permutation in place, O(n).
  • kth-permutation: emit the k-th lex permutation directly via factorial number system, O(n^2) or O(n log n).
  • n-queens: a permutation problem in disguise, column positions form a permutation of rows with diagonal pruning.

How parikshan turns this into a learning loop

Permutations is small but unforgiving: forget the copy or the undo, and the dynamic private tests catch you on n = 5 and beyond. The four-tier hint ladder walks from "position by position" to the full skeleton. Practice mode lets you ask the AI assistant to Explain the used array or Find Bugs in your undo logic without an integrity penalty. Exam mode flips that, every AI nudge docks integrity, and the dispute flow is your safety net if you believe the judge is wrong. Aim to solve permutations in exam mode in five minutes flat; that is the benchmark for moving on to combination-sum.

In the AI-integrated workspace

The agent will write the recursion correctly nine times out of ten. The tenth time it will:

  1. Skip the copy-on-record and ship eight identical permutations.
  2. Forget to clear used[i] on the way back up and miss roughly half the permutations.
  3. Sort the result list at the end "to be safe" instead of sorting the input, wasteful but correct, easy to miss in review.

Your contract with the agent is: name the pattern (permutations with used array), specify the order guarantee (lex via sorted input), and verify the apply/undo pair with one read. That is the entire senior-engineer move. Once you have it on permutations, every backtracking review for the rest of your career follows the same checklist.