Permutations

Overview

A permutation is an ordering of all elements. n distinct elements have n! permutations. Generating them uses backtracking: at each position, try every element not used yet, recurse to fill the next position, then undo.

Two implementations are common: a used[] boolean array with a path, or in-place swapping where you swap each candidate into the current position. With duplicate values, sort and skip a value if an identical earlier value has not been used yet, so identical orderings are not repeated.

When to use it

• All orderings or arrangements of items.
• n is small (n <= 8 to 10; 10! is about 3.6 million).
• The next lexicographic arrangement (next permutation) is needed.
• Permutations with constraints (beautiful arrangements, no adjacent equal letters).

Problem patterns it solves

Where it is used in real software

Key terms

n!

Number of permutations of n distinct items.

used[]

Marks which elements are already in the current path.

Swap-based permutation

Place each candidate at position i by swapping, recurse on i + 1, swap back.

Lexicographic order

Dictionary order of sequences.

How it works, step by step

1. 1
   Base case

   When the path length equals n, record a copy.

2. 2
   Try each unused element

   Loop i from 0 to n - 1, skipping used[i].

3. 3
   Skip duplicates

   After sorting: if nums[i] === nums[i - 1] and !used[i - 1], skip.

4. 4
   Choose, recurse, undo

   used[i] = true; path.push; recurse; path.pop; used[i] = false.

Next permutation of [1, 3, 5, 4, 2]

Find the next larger ordering in lexicographic order, in place

The suffix after i was in decreasing order (its largest arrangement); swapping in the next larger value and reversing the suffix gives the smallest arrangement with the new prefix. O(n), no generation of all permutations.

Implementation

1function permute(nums) {2  const result = [], path = [];3  const used = new Array(nums.length).fill(false);4  function backtrack() {5    if (path.length === nums.length) {6      result.push([...path]);7      return;8    }9    for (let i = 0; i < nums.length; i++) {10      if (used[i]) continue;11      used[i] = true;12      path.push(nums[i]);13      backtrack();14      path.pop();15      used[i] = false;16    }17  }18  backtrack();19  return result;20}21 22// 47. Permutations II23function permuteUnique(nums) {24  nums.sort((a, b) => a - b);25  const result = [], path = [];26  const used = new Array(nums.length).fill(false);27  function backtrack() {28    if (path.length === nums.length) { result.push([...path]); return; }29    for (let i = 0; i < nums.length; i++) {30      if (used[i]) continue;31      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue; // use copies in order32      used[i] = true;33      path.push(nums[i]);34      backtrack();35      path.pop();36      used[i] = false;37    }38  }39  backtrack();40  return result;41}42 43// 31. Next Permutation44function nextPermutation(a) {45  let i = a.length - 2;46  while (i >= 0 && a[i] >= a[i + 1]) i--;47  if (i >= 0) {48    let j = a.length - 1;49    while (a[j] <= a[i]) j--;50    [a[i], a[j]] = [a[j], a[i]];51  }52  for (let l = i + 1, r = a.length - 1; l < r; l++, r--) [a[l], a[r]] = [a[r], a[l]];53}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Wrong duplicate rule.

  Fix: Skip when nums[i] === nums[i - 1] and !used[i - 1]; this forces identical values to be used in index order.

• Forgetting to reverse the suffix in next permutation.

  Fix: After the swap, the suffix is still descending and must be reversed.

• Running full generation for large n.

  Fix: n = 12 is already about 479 million permutations; look for a formula or DP.

Interview questions

Practice problems