Permutations

Generate all permutations of a distinct array — swap-based or used-mask backtracking, n! outputs.

intermediate3 min readUpdated Aug 4, 2026

dsa
backtracking
interview
Google
Meta

The problem

Given an array nums of distinct integers, return all possible permutations. Order of permutations can be anything.

Input:  nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Brute force

Heap’s algorithm or recursive insertion into every position — still Θ(n·n!) work to write all outputs. Backtracking is the interview form.

Optimal: backtracking with used array

function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = Array(nums.length).fill(false);

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

  dfs();
  return res;
}

In-place swap style

function permuteSwap(nums: number[]): number[][] {
  const res: number[][] = [];

  function dfs(start: number): void {
    if (start === nums.length) {
      res.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];
      dfs(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }

  dfs(0);
  return res;
}


Time	O(n · n!)
Space	O(n) aux + O(n·n!) output

Edge cases

Empty → [[]] or [] per convention; LC: one empty perm
Single element
n up to ~8–10 practical for full enumeration

Common bugs

Not copying path (res.push(path) shares reference)
Forgetting to unmark used
Swap version: wrong restore order

Follow-ups

Permutations II — duplicates: sort + skip used identical neighbors
Next permutation
k-th permutation

Interview delivery

Distinct → classic used/swap backtrack.
Show one approach fully.
Complexity n·n!.
Mention duplicate handling if asked.

Decision tree for `[1,2,3]`

Level 0 picks first position (3 choices), level 1 picks second (2 remaining), level 2 last (1). Leaves = 3! = 6. Drawing one branch on the whiteboard prevents off-by-one in the used array.

Swap vs used-array tradeoffs

Style	Mutates input	Extra memory	Easy duplicates variant
used[]	no	O(n) boolean	sort + skip
swap	yes (restore)	O(1) aside from recursion	harder to reason

Prefer used[] unless they ban extra arrays. If they care about restoring nums, note swap mutates during the call even if restored at the end — not thread-safe, not pure.

Complexity you should say

Generating n! permutations, each of length n → output size Θ(n·n!). Any algorithm is Ω(n·n!) just to write the answer. Interview goal is a clean O(n·n!) backtrack without accidental factorial blowups from wrong pruning.