Backtracking (Search with Going Back)

Lesson 5 of 7 · Recursion and backtracking

Backtracking systematically tries all the possibilities, but as soon as it notices that the current attempt cannot succeed, it goes one step back and chooses another possibility. It is used for scheduling, puzzles, subsets and all the tasks in which arrangements have to be found or counted.

Before you start: prerequisites – Introduction to recursion, Recursive algorithms.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea: choose – explore – undo

The solution is built step by step. In every step:

  1. choose one of the possibilities (put a number, a queen, a letter…);
  2. explore – recursively continue building with that choice;
  3. undo the choice (restore the state as it was) and try the next possibility.

All the choices together form a search tree. Backtracking traverses it in depth, and pruning skips the branches that are known in advance not to lead to a solution.

The general form:

void search(int step) {
    if (the solution is complete) {
        process the solution (print it, count it…);
        return;
    }
    for (every possibility p for this step) {
        if (p is allowed) {             // pruning
            apply p;                    // choose
            search(step + 1);           // explore
            undo p;                     // restore the state
        }
    }
}

Example: subsets with a given sum

n natural numbers and a number S are given. How many subsets have the sum exactly S? For every number we choose: we take it or not. If the current sum is already greater than S, there is no point in searching further (the numbers are positive) – that is pruning.

#include <iostream>
#include <vector>
using namespace std;

int n, S;
vector<int> a;
int solutionCount = 0;

void search(int i, int sum) {
    if (sum > S) return;                  // pruning: we have already gone over S
    if (i == n) {                         // we have decided about all the numbers
        if (sum == S) solutionCount++;
        return;
    }
    search(i + 1, sum + a[i]);            // we take a[i]
    search(i + 1, sum);                   // we do not take a[i]
}

int main() {
    cin >> n >> S;
    a.resize(n);
    for (int &x : a) cin >> x;
    search(0, 0);
    cout << solutionCount << endl;
    return 0;
}

For 2 3 5 7 8 and S = 10 the solutions are {2, 3, 5}, {2, 8} and {3, 7}. Here the state does not have to be undone explicitly, because the sum is passed as a parameter.

Example: N queens

N queens have to be placed on an N × N board so that no two of them attack each other. We place the queens row by row; for every column we check whether it is free and whether both diagonals are free. We use three arrays of logical values for occupancy, so the check is instant.

#include <iostream>
using namespace std;

int n, placements = 0;
bool column[20], diag1[40], diag2[40];   // diag1: r + c, diag2: r - c + n

void place(int r) {
    if (r == n) {                        // all the queens have been placed
        placements++;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (column[c] || diag1[r + c] || diag2[r - c + n]) continue;   // an attacked square
        column[c] = diag1[r + c] = diag2[r - c + n] = true;             // choose
        place(r + 1);                                                    // explore
        column[c] = diag1[r + c] = diag2[r - c + n] = false;            // undo
    }
}

int main() {
    cin >> n;
    place(0);
    cout << placements << endl;
    return 0;
}

For N = 8 there are 92 placements. The task with printing the placements and a detailed explanation: N queens – solution.

How fast is backtracking?

In the worst case backtracking traverses the whole search tree, and it is exponentially large (2n subsets, n! permutations). That is why it is used when n is small (usually up to 20–25 for subsets, up to 10–12 for permutations) or when pruning rejects a large part of the tree. If the same states repeat during the search, dynamic programming often helps instead of backtracking.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Binary sequences without two consecutive ones

Print, in lexicographic order, all the binary sequences of length n (n ≤ 15) in which there are no two neighbouring ones.

Example

Input

3

Output

000
001
010
100
101
TASK 02Difficulty: harder

The number of paths through a maze

A maze is an n × m matrix (n, m ≤ 6) in which . marks a passage, and # a wall. How many different paths are there from the top left to the bottom right cell, if you move up, down, left and right and no cell is visited twice?

Example

Input

3 3
...
.#.
...

Output

2
TASK 03Difficulty: harder

Splitting into two teams

n competitors (n ≤ 20) with given strengths have to be split into two teams so that the difference between the sums of the strengths is as small as possible. Print the smallest difference.

Example

Input

5
3 1 4 2 2

Output

0
Common mistakes and tips
  • Every change of the state before a recursive call must have its pair – undoing it after the call.
  • Put the pruning as early as possible: check whether a choice makes sense before you call yourself further.
  • When you only need to know whether a solution exists, stop the search as soon as you find one (the function returns bool).
  • For n over 25–30 pure backtracking is usually too slow – look for cleverer pruning or DP.

Check your knowledge

Open the quiz

Mini quiz: backtracking

1. What does "undo a choice" mean in backtracking?




2. How many nodes are there on the last level of the search tree for the subsets of a set of n elements?




3. What is pruning for?