46. Permutations

Given an array nums of distinct integers, return all possible permutations, in any order.

Positions [0, k) are fixed. Swap each candidate from [k, n) into position k, recurse on k + 1, then swap back.

1function permute(nums: number[]): number[][] {
2  const res: number[][] = [];
3  function dfs(k: number) {
4    if (k === nums.length) { res.push([...nums]); return; }
5    for (let i = k; i < nums.length; i++) {
6      [nums[k], nums[i]] = [nums[i], nums[k]];
7      dfs(k + 1);
8      [nums[k], nums[i]] = [nums[i], nums[k]];
9    }
10  }
11  dfs(0);
12  return res;
13}

k = 0

nums

k,i

results

empty

Keep 1 at position 0.

1 / 0

Space: play/pause · ←/→: step