Permutations

The problem. Given an array nums of distinct integers, return all the possible permutations (orderings), in any order.

Example

nums = [1, 2, 3]  ->  [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
nums = [0, 1]     ->  [[0,1], [1,0]]
nums = [1]        ->  [[1]]

The pattern: permutations and building strings

Here order matters, so the start-index trick from the last chapter no longer applies: after choosing 2, choosing 1 is still allowed. Instead each level may pick any value not used yet, tracked with a used array. The same chapter covers building strings under rules — valid brackets, palindromic pieces — where the rule decides which choices are allowed at each step.

1. Backtracking with a used array

1function permute(nums) {2  const result = [];3  const path = [];4  const used = new Array(nums.length).fill(false);5  const build = () => {6    if (path.length === nums.length) {      // every number placed: one permutation7      result.push([...path]);8      return;9    }10    for (let i = 0; i < nums.length; i++) {11      if (used[i]) continue;                 // already in the path12      used[i] = true;                        // choose13      path.push(nums[i]);14      build();                               // explore15      path.pop();                            // un-choose16      used[i] = false;17    }18  };19  build();20  return result;21}

Time O(n · n!): n! leaves, each copied in O(n). Space O(n) for the path, the used array and the call stack, besides the output.

2. Swap into place

Instead of a separate path, build the permutation inside the array: position i takes each value from i onwards in turn by swapping it in, the rest is permuted recursively, then the swap is undone.

1function permute(nums) {2  const a = [...nums];3  const result = [];4  const fill = (i) => {5    if (i === a.length) {6      result.push([...a]);7      return;8    }9    for (let j = i; j < a.length; j++) {10      [a[i], a[j]] = [a[j], a[i]];   // put a[j] at position i11      fill(i + 1);12      [a[i], a[j]] = [a[j], a[i]];   // swap back13    }14  };15  fill(0);16  return result;17}

Time O(n · n!), space O(n) — no used array or separate path. The permutations come out in a different order, which the problem allows.

Comparing the approaches

Edge cases to test

Variations