Guide to Competitive Programming

Recursion often provides an elegant way to implement an algorithm. In this section, we discuss recursive algorithms that systematically go through candidate solutions to a problem. First, we focus on generating subsets and permutations and then discuss the more general backtracking technique.

  • Generating Subsets

Our first application of recursion is generating all subsets of a set of n elements. For example, the subsets of {1, 2, 3} are ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.
The following recursive function search can be used to generate the subsets. The function maintains a vector

vector<int> subset;

that will contain the elements of each subset. The search begins when the function is called with parameter

void search(int k) {
if (k == n+1) {
// process subset
} else {
// include k in the subset
subset.push_back(k);
search(k+1);
subset.pop_back();
// don’t include k in the subset
search(k+1);
}
}

When the function search is called with parameter k, it decides whether to include the element k in the subset or not, and in both cases, then calls itself with parameter k +1. Then, if k = n +1, the function notices that all elements have been processed and a subset has been generated.
Illustrates the generation of subsets when n = 3. At each function call, either the upper branch (k is included in the subset) or the lower branch (k is not included in the subset) is chosen.

  • Generating Permutations

Next we consider the problem of generating all permutations of a set of n elements. For example, the permutations of {1, 2, 3} are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Again, we can use recursion to perform the search. The following function search maintains a vector

Generating Permutations

vector<int> permutation;

that will contain each permutation, and an array bool chosen[n+1]; which indicates for each element if it has been included in the permutation. The search begins when the function is called without parameters.

void search() {
if (permutation.size() == n) {
// process permutation
} else {
for (int i = 1; i <= n; i++) {
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(i);
search();
chosen[i] = false;
permutation.pop_back();
}
}
}

Each function call appends a new element to permutation and records that it has been included in chosen. If the size of permutation equals the size of the set, a permutation has been generated.

Note that the C++ standard library also has the function next_permutation that can be used to generate permutations. The function is given a permutation, and it produces the next permutation in lexicographic order.

The following code goes through the permutations of {1, 2, . . . , n}:
for (int i = 1; i <= n; i++) {
permutation.push_back(i);
}
do {
// process permutation
} while (next_permutation(permutation.begin(),
permutation.end()));

  • Backtracking

A backtracking algorithm begins with an empty solution and extends the solution step by step. The search recursively goes through all different ways how a solution can be constructed.

As an example, consider the problem of calculating the number of ways n queens can be placed on an n × n chessboard so that no two queens attack each other. For example, shows the two possible solutions for n = 4.

The problem can be solved using backtracking by placing queens on the board row by row. More precisely, exactly one queen will be placed on each row so that no queen attacks any of the queens placed before. A solution has been found when all n queens have been placed on the board.

For example, shows some partial solutions generated by the backtracking algorithm when n = 4. At the bottom level, the three first configurations are illegal, because the queens attack each other. However, the fourth configuration is valid, and it can be extended to a complete solution by placing two more queens on the board.
There is only one way to place the two remaining queens.

Backtracking

The algorithm can be implemented as follows:

void search(int y) {
if (y == n) {
count++;
return;
}
for (int x = 0; x < n; x++) {
if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
search(y+1);
col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
}
}

The search begins by calling search(0). The size of the board is n, and the code calculates the number of solutions to count. The code assumes that the rows and columns of the board are numbered from 0 to n − 1. When search is called with parameter y, it places a queen on row y and then calls itself with parameter y+1. Then, if y = n, a solution has been found, and the value of count is increased by one.

The array col keeps track of the columns that contain a queen, and the arrays diag1 and diag2 keep track of the diagonals. It is not allowed to add another queen to a column or diagonal that already contains a queen.

Shows the numbering of columns and diagonals of the 4 × 4 board. The above backtracking algorithm tells us that there are 92 ways to place 8 queens on the 8 × 8 board. When n increases, the search quickly becomes slow, because
the number of solutions grows exponentially. For example, it takes already about a minute on a modern computer to calculate that there are 14772512 ways to place 16 queens on the 16 × 16 board.

In fact, nobody knows an efficient way to count the number of queen combinations for larger values of n. Currently, the largest value of n for which the result is known is 27: there are 234907967154122528 combinations in this case. This was discovered in 2016 by a group of researchers who used a cluster of computers to calculate the
result.