Permutations

Problem

Given an array of distinct integers, return every possible ordering of its elements. Each output ordering must use every element exactly once, and every distinct arrangement should appear exactly once in the result.

Example. For [1, 2, 3], the output is the six orderings [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Key idea

Unlike subsets, order matters here, and there are n! orderings rather than 2^n subsets, so the enumeration works differently: at each position of the output, choose which still-unused element goes there next.

Build a partial ordering one position at a time. At each step, try placing every unused element in the current position, recurse to fill the remaining positions, then undo that choice (backtracking) before trying the next candidate. Which elements are already placed can be tracked with a boolean "used" array, or by swapping used elements to the front of a working array and recursing only over the remaining suffix. The swap approach avoids the extra tracking structure but needs the swap undone after each call returns, restoring the array for sibling branches. A partial ordering is complete, and gets recorded, once its length equals the input length.

Solution

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

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

    for (let i = 0; i < nums.length; i++) {
      // Skip elements already placed earlier in this ordering.
      if (used[i]) {
        continue;
      }
      // Place nums[i] next and mark it used.
      used[i] = true;
      partial.push(nums[i]);
      backtrack();
      partial.pop();
      // Undo the placement so sibling branches can reuse nums[i].
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

Complexity

• Time: O(n · n!). n! permutations, each costing O(n) to construct.
• Space: O(n). Recursion depth and the used-tracking structure, excluding the output.

Watch out for

• Copy the partial ordering into the results rather than storing a reference to the mutable working array, or every recorded permutation ends up reflecting only its final, fully-backtracked state.
• With the swap-based approach, swap the chosen element back after the recursive call returns, or later branches will see a corrupted array.

Pattern

This is position-by-position backtracking for full orderings, choosing from the remaining pool at each step rather than deciding in or out for each fixed element. It extends directly to permutations with duplicates and to problems needing every ordering under extra constraints, such as N-Queens' column choices.