Graphs · pattern 1 of 8

Backtracking

Build an answer one choice at a time. Make a choice and go on from there. When that path is finished, or cannot work, undo the last choice and try the next one. In this way every possible answer gets built once.

Watch it run in the app

When to use it

Use it when you must return every way to choose, order or place a few items, or find one way that keeps a rule, by trying the choices in turn.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

Ana, Bo and Cy want to enter a quiz for teams of two. Return every team they could send, each team once, with its names in the order given.

Input
names = ["Ana", "Bo", "Cy"]
size = 2

Output
[["Ana", "Bo"], ["Ana", "Cy"], ["Bo", "Cy"]]

The method

Keep a list for the answers and a row for the choices so far
The row is full: record a copy of it and go back
Try each name that stands after the last one chosen
Make the choice, then go on from there
That path is finished: undo the choice, try the next
Start with an empty row, then return everything recorded

The run, one moment at a time

Step 1. No name is chosen yet. The row of choices is empty, and no team is recorded.
```
names: Ana Bo Cy
row: empty
teams: empty
```
Step 4. Choose Ana: it goes into the row. Go on from there. The same job starts again, and it may only take names that stand after Ana.
```
names: Ana Bo Cy
row: Ana
teams: empty
```
Step 2. Choose Bo as well, beside Ana. The row now holds 2 names, so it is a full team: record a copy, Ana+Bo. This path is finished.
```
names: Ana Bo Cy
row: Ana Bo
teams: Ana+Bo
```
Step 5. Back in the job that chose Bo. Take Bo out of the row. The next name, Cy, can now be tried beside Ana.
```
names: Ana Bo Cy
row: Ana Bo
teams: Ana+Bo
```
Step 2. Choose Cy as well, beside Ana. The row now holds 2 names, so it is a full team: record a copy, Ana+Cy. This path is finished.
```
names: Ana Bo Cy
row: Ana Cy
teams: Ana+Bo Ana+Cy
```
Step 5. Back in the job that chose Cy. Take Cy out of the row. No name stands after Cy, so nothing is left to try beside Ana.
```
names: Ana Bo Cy
row: Ana Cy
teams: Ana+Bo Ana+Cy
```
Step 5. Every path that starts with Ana is finished. Take Ana out, and the row is empty again. Bo is the next name to try.
```
names: Ana Bo Cy
row: Ana
teams: Ana+Bo Ana+Cy
```
Step 4. Now choose Bo for the first place and go on from there. Only names that stand after Bo may join it.
```
names: Ana Bo Cy
row: Bo
teams: Ana+Bo Ana+Cy
```
Step 2. Choose Cy as well, beside Bo. The row now holds 2 names, so it is a full team: record a copy, Bo+Cy. This path is finished.
```
names: Ana Bo Cy
row: Bo Cy
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 5. Back in the job that chose Cy. Take Cy out of the row. No name stands after Cy, so nothing is left to try beside Bo.
```
names: Ana Bo Cy
row: Bo Cy
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 5. Every path that starts with Bo is finished. Take Bo out, and the row is empty again. Cy is the next name to try.
```
names: Ana Bo Cy
row: Bo
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 4. Now choose Cy for the first place and go on from there. Only names that stand after Cy may join it.
```
names: Ana Bo Cy
row: Cy
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 3. No name stands after Cy, so there is nothing to try. A team that starts with Cy cannot be completed: this path cannot work.
```
names: Ana Bo Cy
row: Cy
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 5. Every path that starts with Cy is finished. Take Cy out, and the row is empty again. Every name has had its turn in the first place.
```
names: Ana Bo Cy
row: Cy
teams: Ana+Bo Ana+Cy Bo+Cy
```
Step 6. Nothing is left to try, so every path has been followed. 3 teams were recorded, each built exactly once: Ana+Bo, Ana+Cy and Bo+Cy.
```
names: Ana Bo Cy
row: empty
teams: Ana+Bo Ana+Cy Bo+Cy
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(names, size) {
  // 1. Keep a list for the answers and a row for the choices so far
  const teams = [];
  const row = [];
  function extend(start) {
    // 2. The row is full: record a copy of it and go back
    if (row.length === size) {
      teams.push([...row]);
      return;
    }
    // 3. Try each name that stands after the last one chosen
    for (let i = start; i < names.length; i++) {
      // 4. Make the choice, then go on from there
      row.push(names[i]);
      // extend calls itself: the same job, one name further.
      extend(i + 1);
      // 5. That path is finished: undo the choice, try the next
      row.pop();
    }
  }
  // 6. Start with an empty row, then return everything recorded
  extend(0);
  return teams;
}

Python

def solve(names, size):
    # 1. Keep a list for the answers and a row for the choices so far
    teams = []
    row = []

    def extend(start):
        # 2. The row is full: record a copy of it and go back
        if len(row) == size:
            teams.append(row.copy())
            return
        # 3. Try each name that stands after the last one chosen
        for i in range(start, len(names)):
            # 4. Make the choice, then go on from there
            row.append(names[i])
            # extend calls itself: the same job, one name further.
            extend(i + 1)
            # 5. That path is finished: undo the choice, try the next
            row.pop()

    # 6. Start with an empty row, then return everything recorded
    extend(0)
    return teams

How to spot it

Asked: Return every possible way, or all the ways that keep a rule: Every way must be built, so each one is made choice by choice. Undoing a choice lets the next way reuse the part before it.
Limits: The input has at most about 20 items: Trying every way grows very fast: 20 yes-or-no choices give 1,048,576 ways. A limit this small says that trying them all is expected.
Asked: Place the pieces so that no rule is broken: A rule can be tested after each piece. A piece that breaks it is taken back at once, with everything that would have followed.
Given: A path may not use the same cell twice: A cell is marked while the path stands on it. The mark is removed on the way back, so that another path may use the cell.

Looks like it, but is not

You must count the ways, or find the best total, and need not list them. Use One-dimensional dynamic programming. A count can be put together from the counts of smaller inputs. No single way is ever built, so much larger inputs are possible.
You walk a grid or a graph and must reach every place you can. Use Graph traversal with a visited set. There a place stays marked to the end, because reaching it once is enough. Here a mark is removed on the way back.
At each step a rule tells you which choice is safe, so nothing is undone. Use Greedy choice. When the right choice is known every time, one pass is enough. Trying the other choices would only repeat work.

Cost and mistakes

Time is the number of ways times the length of one, since each way is built and copied: for n yes-or-no choices, n times 2 to the power n, written O(n * 2^n). Extra space beside the answers is the row, never longer than n.

Watch out

Record a copy of the row, not the row itself. The row keeps changing after it is recorded, so without a copy every recorded answer ends up as the same empty row.
Undo exactly what you did, straight after the call comes back. If the undo is missing, the old choice stays in the row and every later answer is wrong.

In the 150

10 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 10

Generate ParenthesesMedium · Backtracking
SubsetsMedium · Backtracking
Combination SumMedium · Backtracking
PermutationsMedium · Backtracking
Subsets IIMedium · Backtracking
Combination Sum IIMedium · Backtracking
Word SearchMedium · Backtracking
Palindrome PartitioningMedium · Backtracking
Letter Combinations of a Phone NumberMedium · Backtracking
N QueensHard · Backtracking