Permutations

The problem

You are given a list of integers, nums, in which no value repeats. Return every permutation of it. A permutation is one way to put all the values in a row, with each value used exactly once: [1, 2] and [2, 1] are the two permutations of [1, 2]. Return each permutation once, as a list. The permutations may come in any order, but the order inside each one is what tells them apart. An empty nums has one permutation, the empty row, so return a list that holds one empty list.

What to write

function solve(nums: number[]): number[][]

Input
nums = [1,2]

Output
[[1,2],[2,1]]

Input
nums = [0,1]

Output
[[0,1],[1,0]]

Constraints

0–7 distinct integers; output ordering is unrestricted.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 7 values and no value repeats, so two different orders never look the same. Seven values can be lined up in 5,040 ways, few enough to write out one by one. An empty list still has one order, the empty one, so its answer is a list that holds one empty list.

2. Hint 2: Ask a smaller question

   Line up 1, 2 and 3 by hand. If 1 goes in the first place, which values can go in the second place? Once two places are filled, how many choices are left for the third? What do you have to keep track of while you fill the places?

3. Hint 3: Name the pattern

   The signal is "return every way to order the values". Fill the row one place at a time. For each place, try every value that is not in the row yet: put it in, fill the remaining places in every possible way, then take it out and try the next value. Choosing, exploring and undoing like this is backtracking. Read the lesson on backtracking.

4. Hint 4: State the invariant

   The row never holds a value twice, and a value is marked as used exactly while it is in the row. When a call returns, the row and the marks are exactly as they were when that call started, so the next choice starts clean.

5. Hint 5: Sketch the pseudocode

   Keep a list of answers and one used mark per position, all off. fill(row): if row has as many values as nums, record a copy and return. For each position i that is not marked: mark it, add the value at i to row, call fill(row), then remove the value and clear the mark. Start with fill(empty row).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Build a path by choosing an unused index. Mark it used before recursion and undo that choice after returning.

The slow way

Fill every place with every value and throw away the rows that use a value twice. For three values that is 27 rows, such as [1, 1, 1] and [1, 1, 2], and only 6 of them repeat nothing. It is correct, but the waste grows fast: seven values give 823,543 rows for 5,040 answers.

The insight

A row goes wrong the moment a value is used a second time, so there is no need to wait until the row is full to find out. Remember which values are already in the row and offer only the others to the next place. Every row you finish is then a real order, and nothing is built to be thrown away.

Step by step

1. Keep a list for the answers and a used mark for each position. The marks answer "is this value already in the row?" in one step, without searching the row. They all start off, because the row starts empty.
2. Extend the row built so far by one more value. One call fills one place. The row and the marks are shared by all the calls, so a call sees everything that was placed before it.
3. Every value is in the row: record a copy of the row. A row as long as nums that repeats nothing is one complete order. A copy is stored because the shared row is about to be changed again.
4. Try each value that is not in the row yet. Any value that is still free may take the next place, and each one leads to different orders. A marked value is skipped, because every value appears once.
5. Mark the value, add it to the row and fill the rest of the row. The mark keeps the deeper calls from choosing this value again. The inner call then records every order that begins with the row as it stands now.
6. Take the value out again and clear its mark. The next value in the loop must start from the row as this call found it. Left undone, the old value would stay in the row and stay marked, so it could never be chosen for another place.
7. Start with an empty row and return everything recorded. Nothing is placed and nothing is marked at the start. The first call tries every value in the first place, so no order is missed.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Keep a list for the answers and a used mark for each position
  const out = [],
    used = Array(nums.length).fill(false);
  // 2. Extend the row built so far by one more value
  function visit(path) {
    // 3. Every value is in the row: record a copy of the row
    if (path.length === nums.length) {
      out.push([...path]);
      return;
    }
    // 4. Try each value that is not in the row yet
    for (let i = 0; i < nums.length; i++)
      if (!used[i]) {
        // 5. Mark the value, add it to the row and fill the rest of the row
        used[i] = true;
        path.push(nums[i]);
        visit(path);
        // 6. Take the value out again and clear its mark
        path.pop();
        used[i] = false;
      }
  }
  // 7. Start with an empty row and return everything recorded
  visit([]);
  return out;
}

function solve(nums: number[]): number[][] {
  // 1. Keep a list for the answers and a used mark for each position
  const out: number[][] = [],
    used = Array(nums.length).fill(false);
  // 2. Extend the row built so far by one more value
  function visit(path: number[]): void {
    // 3. Every value is in the row: record a copy of the row
    if (path.length === nums.length) {
      out.push([...path]);
      return;
    }
    // 4. Try each value that is not in the row yet
    for (let i = 0; i < nums.length; i++)
      if (!used[i]) {
        // 5. Mark the value, add it to the row and fill the rest of the row
        used[i] = true;
        path.push(nums[i]);
        visit(path);
        // 6. Take the value out again and clear its mark
        path.pop();
        used[i] = false;
      }
  }
  // 7. Start with an empty row and return everything recorded
  visit([]);
  return out;
}

def solve(nums):
    # 1. Keep a list for the answers and a used mark for each position
    result = []
    used = [False] * len(nums)

    # 2. Extend the row built so far by one more value
    def backtrack(path):
        # 3. Every value is in the row: record a copy of the row
        if len(path) == len(nums):
            result.append(path.copy())
            return
        # 4. Try each value that is not in the row yet
        for i, num in enumerate(nums):
            if not used[i]:
                # 5. Mark the value, add it to the row and fill the rest of the row
                used[i] = True
                path.append(num)
                backtrack(path)
                # 6. Take the value out again and clear its mark
                path.pop()
                used[i] = False

    # 7. Start with an empty row and return everything recorded
    backtrack([])
    return result

Example 1, traced

Input
nums = [1,2]

Output
[[1,2],[2,1]]

Why it works

A value is marked exactly while it is in the row, so the row never repeats a value and a full row is a real order. Every order is found: its first value is one of the first call's choices, its second value one of the next call's, and so on. Two orders differ at some place, where the search made different choices, so none is recorded twice.

Time and space

Time O(n × n!), extra space O(n × n!) output. n values can be lined up in n! ways: n choices for the first place, then one fewer each time. The search makes under three calls per finished row, and each call loops over the n positions: O(n × n!) time. The answer holds n! rows of n values.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Clear the mark when you take a value out of the row. If the mark stays on, the value is never offered again, and [1, 2] returns only [1, 2].
• Let every call look at all the values, not only at those after the last one chosen. That rule belongs to combinations. Here it finds a single order: [1, 2, 3] returns only [1, 2, 3].
• Record a copy of the row, not the row itself. Every entry would be the one shared row, which is empty again when the search ends: [1, 2] returns two empty lists.

Pattern

Backtracking. Builds on Generate Parentheses and Subsets.

Keep going