Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Permutations

Problem (restated)

Given a list of distinct integers, return all possible permutations.

Intuition

Backtracking: choose an unused number, recurse, undo. When path length == n, record a copy.

Approaches

Backtracking with used flags

Unverified

Time O(n · n!)Space O(n)

Idea. path list + used boolean array. Try each unused index, recurse, pop.

Walkthrough. [1,2,3] explores 6 permutations.

Trade-offs. Swap-based in-place generation uses less auxiliary memory for path but is harder to read.

Solution

export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    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;
}

export function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const used = new Array(nums.length).fill(false);
  const dfs = () => {
    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;
}

Template connection

Choose / explore / undo. pure backtracking template.

Reflection

used[i] skips a value you already picked. There are n! leaves. Forget to clear the flag on the way back and the next branch is missing choices.
Values are unique. Swapping and swapping back builds the same tree.
One element is one permutation. An empty array has one empty answer.