Permutations

Examples

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

There are 3! = 6 ways to arrange three distinct numbers.

Input: nums = [0, 1]
Output: [[0,1], [1,0]]

Two numbers can be arranged in 2! = 2 ways.

Constraints

• 1 <= nums.length <= 6

• All numbers in nums are unique.

Approach

Build one arrangement at a time, one position at a time. At each position, try placing every number that hasn't already been used earlier in this same arrangement, then move on to fill the next position. When every position is filled, you've completed one full permutation.

The natural way to track "already used" is a small tracker (an array of booleans) alongside the arrangement you're building. Before placing a number, check it isn't already used; after exploring everything that follows from placing it, mark it unused again before trying the next candidate for that position - the same try/explore/undo rhythm as before, just applied to positions in an arrangement instead of yes/no inclusion decisions.

There's also a neat trick that avoids the tracker altogether: keep the numbers in a single array, and instead of asking "which unused number goes here", swap the number currently in this position with each candidate further down the array, recurse, and then swap back. Everything before the current position is "locked in", and everything from the current position onward is still "up for grabs" - so you never need a separate structure to remember what's used.

Solutions

Backtracking — Track Used Numbers

Build the current arrangement in an array, alongside a parallel boolean array marking which numbers are already placed. At each position, try every number that isn't marked used: mark it used, place it, recurse into the next position, then unmark it and remove it before trying the next candidate.

function permute(nums) {
  const result = [];
  const current = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    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.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

Time: O(n * n!) · Space: O(n) auxiliary (used array + recursion + current array), plus O(n * n!) output

Optimal — In-Place Swapping

Instead of a separate "used" tracker, treat everything before the current position as locked in and everything from the current position onward as the pool of numbers still available. To try a candidate for the current position, swap it into place, recurse on the next position, then swap back to undo it - freeing up that spot for the next candidate without needing any extra bookkeeping array.

function permute(nums) {
  const result = [];

  function backtrack(start) {
    if (start === nums.length) {
      result.push([...nums]);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]];

      backtrack(start + 1);

      [nums[start], nums[i]] = [nums[i], nums[start]]; // swap back
    }
  }

  backtrack(0);
  return result;
}

Time: O(n * n!) · Space: O(n) recursion depth only (no separate tracker), plus O(n * n!) output