Permutations (backtracking)

Medium TimeO(n · n!) SpaceO(n)

A permutation is one arrangement of all the values, so three values have six. Given a list nums of distinct values, return every ordering of them. Each value is used exactly once in every ordering, and the orderings may come back in any order as long as none is missing or repeated.

Examples

Example 1

Input
nums = [1, 2, 3]
Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
3 × 2 × 1 = 6 arrangements: three choices for the first place, two for the second, one for the last.

Example 2

Input
nums = [1, 2]
Output
[[1,2],[2,1]]
2 × 1 = 2, and swapping the pair is the only thing that can be done.

The Code

function permute(nums) {
  if (nums.length <= 1) return [nums];
  const out = [];
  for (let i = 0; i < nums.length; i++) {
    const rest = [...nums.slice(0, i), ...nums.slice(i + 1)];
    for (const p of permute(rest)) {
      out.push([nums[i], ...p]);
    }
  }
  return out;
}
permute([1, 2, 3]);
Done

The first 34 calls, of 44. This one does not fit on a page.

Step through permute([1, 2, 3]) call by call

More like this

All backtracking examples (10) →