46. Permutations

List every possible ordering of a set of distinct integers. The key move is classic backtracking: choose a number, recurse, then undo the choice — so every branch of the decision tree is explored exactly once.

● MediumBacktrackingRecursionDecision TreeTypeScript

PROBLEM What we're solving

Given an array of distinct integers, return all possible permutations (every full-length arrangement) in any order. nums = [1, 2, 3] produces six arrangements: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]. For n distinct numbers there are always exactly n! results.

KEY IDEA Build the arrangement slot by slot; undo each choice after recursing

Insight → treat the problem as a decision tree. At each level pick any unused number, place it in the next slot, and recurse. When the path reaches length n you are at a leaf — record it. After the recursive call returns, undo the choice (pop from the path, mark unused) so the same slot can try a different number. The backtrack step is what makes exhaustive search efficient: it reuses state instead of copying it on every branch.

RECIPE Choose, recurse, undo — three moves, repeat

0 · Initialise. Create a used[n] boolean mask (all false) and an empty current path. These are mutated in-place throughout.
1 · Base case. When current.length === n push a snapshot ([...current]) into result and return. The spread is critical — without it every entry in result would alias the same array.
2 · Try each candidate. Loop i = 0..n-1. If used[i], skip. Otherwise: set used[i] = true, push nums[i] onto current, and call backtrack(current).
3 · Undo (backtrack). After the recursive call returns, pop current and reset used[i] = false. The state is exactly as it was before step 2 — the next iteration can safely try nums[i+1].

Classic confusion → forgetting to spread when recording the leaf. result.push(current) stores a reference; every entry ends up pointing to the same array, which will be empty by the time you read it. Always push [...current].

COST Complexity & alternatives

Copy-on-every-call

O(n · n!)

Pass a new array slice each call — extra O(n) per node.

Mutate + undo (used mask)

O(n · n!)

Same big-O but constant factor is smaller — one array, no copies.

The output itself is O(n · n!) — you must produce n! permutations each of length n, so this is optimal. The call tree has O(n!) leaves and O(n · n!) total nodes.

Swap-in-place variant: instead of a used mask, swap nums[start] with each nums[i], recurse with start+1, then swap back. Avoids the mask but mutates the input array.

Pattern transfer → the same choose / recurse / undo skeleton drives Subsets (LC 78), Combinations (LC 77), Combination Sum (LC 39), N-Queens (LC 51), and Word Search (LC 79). Once you can write permutations from memory, you can adapt the template to any of those in under two minutes.

RUN IT Backtrack: choose, recurse, undo

nums =

step 0 / 37

STARTStart: find all permutations of [1, 2, 3]. path is empty, all 3 numbers are free.

1▶function permute(nums: number[]): number[][] {
2▶  const result: number[][] = [];
3▶  const used: boolean[] = new Array(nums.length).fill(false);
4 
5  function backtrack(current: number[]): void {
6    if (current.length === nums.length) {
7      result.push([...current]);   // leaf: full-length arrangement — record it
8      return;
9    }
10    for (let i = 0; i < nums.length; i++) {
11      if (used[i]) continue;       // skip already-placed numbers
12      used[i] = true;
13      current.push(nums[i]);
14      backtrack(current);          // recurse one level deeper
15      current.pop();               // undo the choice
16      used[i] = false;
17    }
18  }
19 
20▶  backtrack([]);
21  return result;
22}

1free2free3free

State

[]

path

—

chosen

[F, F, F]

used

depth

results

[]

result[]

used (in path)current choicepermutation recordedchosen element / depth

slowfast

TYPESCRIPT The solution, annotated

permute.ts
function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const used: boolean[] = new Array(nums.length).fill(false);

  function backtrack(current: number[]): void {
    if (current.length === nums.length) {
      result.push([...current]);   // leaf: full-length arrangement — record it
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;       // skip already-placed numbers
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);          // recurse one level deeper
      current.pop();               // undo the choice
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Reading it block by block

Lines 2–3 — shared mutable state. result accumulates completed arrangements. used is a boolean mask: used[i] is true when nums[i] is already in the current path. Both are declared in the outer scope and mutated in-place — this is what makes the undo step possible.

Lines 5–8 — base case (the leaf). When the path is full (current.length === nums.length) we have a complete permutation. Push a snapshot ([...current]) and return. Without the spread every slot in result would alias the same array object, which ends up empty.

Lines 9–12 — try each unused number. The loop runs over all indices. If used[i] is set, skip. Otherwise flag it used, append to current, and recurse. This is the “choose” half of the backtrack pair.

Lines 13–14 — undo the choice.After the recursive call returns, pop the last element and clear the flag. The state is restored to exactly what it was before the choice — the next iteration can safely try a different number in the same slot. This is the “backtrack” step, and it is what distinguishes backtracking from a naive exponential enumeration.

Complexity → Time: O(n · n!) — there are n! leaves and each costs O(n) to record. Space: O(n) for the recursion stack and used mask (not counting the output).

INTERVIEWFollow-ups they'll ask

“Permutations II (with duplicates)?” Sort the input first, then skip a candidate if it equals the previous one AND the previous one is not currently used — this prunes duplicate branches without a visited set.
“Return only the k-th permutation?” (LC 60) Use the factorial-number system: at each slot, divide k by (remaining - 1)! to pick the digit directly — no backtracking needed.
“Generate iteratively (no recursion)?”Heap's algorithm or next-permutation (sort, find rightmost ascent, swap, reverse suffix) both work in O(n) per step.
“How would you handle very large n?” Stream permutations one at a time with a generator (function*) instead of collecting all n! into memory.
“Swap-in-place variant?” Swap nums[start] with nums[i], recurse on start + 1, swap back. Eliminates the used array but mutates the input.

OPTIMAL Backtracking

permute.ts
function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const used: boolean[] = new Array(nums.length).fill(false);

  function backtrack(current: number[]): void {
    if (current.length === nums.length) {
      result.push([...current]);   // leaf: full-length arrangement — record it
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;       // skip already-placed numbers
      used[i] = true;
      current.push(nums[i]);
      backtrack(current);          // recurse one level deeper
      current.pop();               // undo the choice
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Complexity → Time: O(n · n!) — there are n! leaves and each costs O(n) to record. Space: O(n) for the recursion stack and used mask (not counting the output).

ALT 1 Brute force — generate all length-n tuples, keep the distinct ones

O(n · nⁿ) time · O(n · n!) space

Enumerate every sequence of n positions where each position independently picks any of the n values (so nⁿ tuples in all), then discard any tuple that reuses an element. What survives is exactly the set of permutations.

approach-2.ts
function permute(nums: number[]): number[][] {
  const n = nums.length;
  const result: number[][] = [];
  const current: number[] = [];

  function build(slot: number): void {
    if (slot === n) {
      // Keep only tuples that used n distinct elements.
      if (new Set(current).size === n) result.push([...current]);
      return;
    }
    for (let i = 0; i < n; i++) {
      current.push(nums[i]);   // no used-check: every value is allowed here
      build(slot + 1);
      current.pop();
    }
  }

  build(0);
  return result;
}

Note → Without the used mask the search explores all nⁿ tuples and throws away the overwhelming majority (only n! of them are valid) — e.g. for n = 8 that is 16.7M tuples to surface 40K answers. Skipping already-placed elements with the used[] mask prunes every dead branch up front, recovering the optimal O(n · n!).

MNEMONIC The one-liner

"Mark it used, recurse, unmark — the undo step is what makes it backtracking."

TRIGGERS When you see _ → reach for _

"all arrangements / orderings"	backtrack with used[] mask
choose one from remaining, repeat until full	backtrack choose/recurse/undo
"n! results" in constraints	backtrack leaf-record pattern
subsets / combinations / permutations family	same skeleton, different base/loop

SKELETON The reusable shape

skeleton.ts
const result: number[][] = [];
const used: boolean[] = new Array(nums.length).fill(false);

function backtrack(current: number[]): void {
  if (current.length === nums.length) {
    result.push([...current]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true;
    current.push(nums[i]);
    backtrack(current);
    current.pop();
    used[i] = false;
  }
}
backtrack([]);
return result;

FLASHCARDS Tap to flip

What is the base case in permutation backtracking?

When current.length === nums.length — a full-length path is a leaf. Push [...current] (spread!) and return.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

How many permutations does [1, 2, 3] produce?

QUESTION 02

What is the time complexity of generating all permutations with the backtrack + used-mask approach?

QUESTION 03

A student writes result.push(current) instead of result.push([...current]). What happens?

QUESTION 04

What is the purpose of setting used[i] = false after the recursive call?

QUESTION 05

Trace permute([1, 2]). What is the correct output?

QUESTION 06

What change is needed to solve Permutations II (with duplicate numbers)?

QUESTION 07

In the swap-in-place variant of permutations, what is swapped back after recursion?

QUESTION 08

#46 · PermutationsGenerate all n! permutations via backtracking with a boolean "used" array: at each depth pick any unused element, mark it, recurse, then unmark. Record the path when its length equals n.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Build the arrangement slot by slot; undo each choice after recursing

RECIPE Choose, recurse, undo — three moves, repeat

COST Complexity & alternatives

RUN IT Backtrack: choose, recurse, undo

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Backtracking

ALT 1 Brute force — generate all length-n tuples, keep the distinct ones

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _