#55

Permutations

medium

arraybacktracking

Given an array nums of distinct integers, return all the possible permutations of its elements.

A permutation is an arrangement of every element exactly once; for n distinct numbers there are n! of them. You may return the list of permutations in any order, but each individual permutation must use every element exactly once in the order you place them.

Example

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

All 3! = 6 orderings.

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All integers of nums are distinct.

Intuition

A first attempt recurses position by position, and at each position asks the path itself which numbers are still free: scan the numbers already placed, and try any nums[i] that doesn't show up in that scan. Once every position is filled, the path is one complete permutation.

function permute(nums) {
  const result = [];
  const path = []; // the permutation currently being built

  function backtrack() {
    // Base case: every position is filled — record a copy of the permutation.
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      // Naive "already placed?" check: rescan the whole path so far. O(n) per check.
      if (path.includes(nums[i])) continue;
      path.push(nums[i]); // choose
      backtrack();        // explore with nums[i] locked in
      path.pop();         // un-choose (backtrack) before trying the next index
    }
  }

  backtrack();
  return result;
}

Brute force — same recursive shape, but "already placed" is answered by scanning the path: O(n² · n!).

This already explores the right search tree — position by position, try an unused number, recurse, undo — so it isn't a different algorithm, just a slower way to answer one question: is this number already in the path? Scanning the path for that answer costs O(n), and it gets asked at every one of the n candidate indices, at every one of the n positions, across n! completed permutations — turning an already-large O(n · n!) enumeration into O(n² · n!). Can we do better?

The key observation: membership doesn't need a scan at all. A used boolean array, one flag per index, answers "is index i already placed?" in O(1) — the same trade a hash map makes for membership generally, just specialized to a plain array since positions are already small, dense integers.

The stored solution keeps the identical recursive shape — same path, same push/recurse/pop — and only swaps the O(n) path.includes check for an O(1) used[i] flag, flipped on when a position is chosen and back off on the way out.

Walking it through:

nums = [4, 6, 9]

i↓

path=[]; used[0]=false → place nums[0]=4

Start at depth 0 with an empty path. Try index 0 first: it's unused, so place 4 and mark index 0 used.

i↓

path=[4]; used[1]=false → place nums[1]=6

Depth 1: index 0 (struck through) is already used, so move to index 1. It's free — place 6.

i↓

path=[4,6]; used[2]=false → place nums[2]=9 → record [4,6,9]

Depth 2: only index 2 is still unused. Place 9 — the path now has length 3, a full permutation, so record [4, 6, 9].

i↓

pop 9, unmark index 2 → depth 2 has no other free index → pop 6, unmark index 1

Backtrack: undo the last placement and look for another candidate at that depth — but depth 2 already tried its only free index (index 2), so unwind one level to depth 1 and undo 6 too, where index 2 is still untried.

i↓

path=[4]; used[2]=false → place nums[2]=9 → path=[4,9]

Back at depth 1 with just index 0 used, try the next candidate: index 2. Place 9, then depth 2 has only index 1 left — place 6 and record [4, 9, 6].

i↓

unwind to depth 0 → try index 1, then index 2 as the first placement

Once both orderings starting with 4 are recorded, unwind fully and start over with index 1 (6) and then index 2 (9) as the first element — the same nested process repeats under each, producing all 3! = 6 permutations.

Optimization

Backtracking with used flags

Build each permutation position by position. Keep a used flag per index; at each depth, try every not-yet-used element, mark it, recurse, then unmark on the way back. When the path reaches full length, record a copy.

O(n · n!) time (each of the n! permutations costs O(n) to copy), O(n) recursion depth.

function permute(nums) {
  const result = [];
  const path = []; // the permutation currently being built, one position at a time
  const used = new Array(nums.length).fill(false); // used[i] = true once nums[i] is already in path
  const dfs = () => {
    // Base case: every position is filled — record a copy of the completed permutation.
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    // Try every index as the next position, skipping any value already placed.
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; // choose nums[i] for this position
      path.push(nums[i]);
      dfs(); // recurse into the next position with nums[i] locked in
      path.pop(); // undo the choice (backtrack)...
      used[i] = false; // ...so a later branch can use nums[i] again
    }
  };
  dfs();
  return result;
}

Complexity analysis

Time complexity: O(n · n!). Here's why:

The recursion produces exactly n! complete permutations — one leaf per full-length path.
Reaching each leaf takes n recursive calls (one per position filled), and recording it copies the n-length path — both O(n) per leaf.
The used array answers every "is this index free?" check in O(1), so no extra factor is added beyond the n! leaves and their O(n) cost.

So the total work is n! × O(n) = O(n · n!).

Space complexity: O(n) auxiliary. Here's why:

The used array and the path array each hold at most n entries.
The recursion stack is at most n frames deep, one per position filled.

So the extra bookkeeping is O(n). The result array itself holds n! permutations of length n — O(n · n!) — but that's the required output, not overhead the algorithm adds.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [8]	[[8]]	Single element — smallest possible input, only one arrangement.
nums = [4,-3]	[[4,-3],[-3,4]]	Two elements, one negative — both orderings.
nums = [6,3]	[[6,3],[3,6]]	Two positive elements — the other direction of the pair swap.
nums = [2,-4,7]	[[2,-4,7],[2,7,-4],[-4,2,7],[-4,7,2],[7,2,-4],[7,-4,2]]	Three elements spanning positive and negative — the full 3! = 6 branch from the walkthrough's shape.
nums = [-10,0,10]	[[-10,0,10],[-10,10,0],[0,-10,10],[0,10,-10],[10,-10,0],[10,0,-10]]	Both constraint boundaries plus zero — still just 3! = 6 orderings, no special-casing needed.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor