medium

Permutations

Return every possible ordering of a list of unique numbers.

1. Define the problem

Permutations

Given an array nums of distinct integers, return all the possible permutations . You can return the answer in any order. Use backtracking that fills one slot at a time: try each unused element in that slot, recurse into the next slot, then undo the choice — marking the element unused again — so a different slot can use it.

Constraints

  • 1 ≤ nums.length ≤ 6
  • -10 ≤ numsi ≤ 10
  • All integers are unique

Example

Inputnums = [1, 2, 3]
Output[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Explanation Every one of the 3! = 6 orderings of [1, 2, 3] is a valid permutation.

2. Know the words first

In plain terms

Permutation
An ordering of a set of items — unlike a combination, the order matters, so [1, 2] and [2, 1] count as two different permutations.
3. Visualize the solution

Fill each slot with an unused element, undo to free it for the next branch

Fill each slot with an unused element, undo to free it for the next branch
Statustry

Slot 0 tries index 0 (value 1): path=[1].

What happens in this step

path = [1], used = [T, F, F]
choice: index 0 (value 1), try continuing

Slot 0 tries the first unused element, index 0 (value 1). used[0] is marked true and 1 is pushed onto path before recursing into slot 1.
Step 1 of 5

Steps to visualize

  1. Try an unused element for the next open slot and mark it used.
  2. Recurse to fill the next slot the same way.
  3. Once every slot is filled, record the path as one permutation.
  4. Undo the last choice — mark that element unused again — so the previous slot can try a different element.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill each slot with an unused element, undo to free it for the next branch
Statustry

Slot 0 tries index 0 (value 1): path=[1].

What happens in this step

path = [1], used = [T, F, F]
choice: index 0 (value 1), try continuing

Slot 0 tries the first unused element, index 0 (value 1). used[0] is marked true and 1 is pushed onto path before recursing into slot 1.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {
      result.push(path.slice());
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}
Time
O(n · n!)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 2, 3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]example from the docstring
nums = [0, 1][[0,1],[1,0]]two elements, includes zero
nums = [1][[1]]smallest valid input, a single element
nums = [1, 2][[1,2],[2,1]]boundary case, exactly two elements
nums = [-1, 0][[-1,0],[0,-1]]negative values mixed with zero
nums = [7, 8, 9][[7,8,9],[7,9,8],[8,7,9],[8,9,7],[9,7,8],[9,8,7]]three elements with non-consecutive-looking values

Keep reading