## Table of Contents

SubsetsResourcesSolution - Apple DivisionGenerating Subsets RecursivelyGenerating Subsets with BitmasksPermutationsLexicographical OrderSolution - Creating Strings IGenerating Permutations RecursivelyGenerating Permutations Using next_permutationBacktrackingResourcesSolution - Chessboard & QueensBy Generating PermutationsUsing BacktrackingProblems# Complete Search with Recursion

Author: Many

Contributors: Darren Yao, Sam Zhang, Michael Cao, Andrew Wang, Benjamin Qi, Dong Liu, Maggie Liu, Dustin Miao

Harder problems involving iterating through the entire solution space, including those that require generating subsets and permutations.

### Prerequisites

## Table of Contents

SubsetsResourcesSolution - Apple DivisionGenerating Subsets RecursivelyGenerating Subsets with BitmasksPermutationsLexicographical OrderSolution - Creating Strings IGenerating Permutations RecursivelyGenerating Permutations Using next_permutationBacktrackingResourcesSolution - Chessboard & QueensBy Generating PermutationsUsing BacktrackingProblems### Warning!

Although knowledge of recursion is not strictly necessary for Bronze, we think that it makes more sense to include this module as part of Bronze rather than Silver.

## Subsets

Focus Problem – try your best to solve this problem before continuing!

### Resources

Resources | ||||
---|---|---|---|---|

CPH | good explanation + code, no need to repeat |

### Solution - Apple Division

Since $n \le 20$, we can solve this by trying all possible divisions of $n$ apples into two sets and finding the one with the minimum difference in weights. Here are two ways to do this.

#### Generating Subsets Recursively

The first method would be to write a recursive function which searches over all possibilities.

At some index, we either add $\texttt{weight}_i$ to the first set or the second set, storing two sums $\texttt{sum}_1$ and $\texttt{sum}_2$ with the sum of values in each set.

Then, we return the difference between the two sums once we've reached the end of the array.

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;int n;vector<long long> weights;ll recurse_apples(int index, ll sum1, ll sum2) {// We've added all apples- return the absolute differenceif (index == n) { return abs(sum1 - sum2); }

Java

import java.io.*;import java.util.*;public class AppleDivision {static int n;static int[] weights;public static void main(String[] args) throws Exception {Kattio io = new Kattio();

Python

n = int(input())weights = list(map(int, input().split()))def recurse_apples(i: int, sum1: int, sum2: int) -> int:# We've added all apples- return the absolute differenceif i == n:return abs(sum2 - sum1)# Try adding the current apple to either the first or second set

#### Generating Subsets with Bitmasks

### Warning!

You are not expected to know this for Bronze.

A **bitmask** is an integer whose binary representation is used to represent a
subset. In the context of this problem, if the $i$'th bit is equal to $1$ in a particular bitmask,
we say the $i$'th apple is in $s_1$. If not, we'll say it's in $s_2$.
We can iterate through all subsets $s_1$ if we check all bitmasks ranging from
$0$ to $2^N-1$.

Let's do a quick demo with $N=3$. These are the integers from $0$ to $2^3-1$ along with their binary representations and the corresponding elements included in $s_1$. As you can see, all possible subsets are accounted for.

Number | Binary | Apples In $s_1$ |
---|---|---|

0 | `000` | $\{\}$ |

1 | `001` | $\{0\}$ |

2 | `010` | $\{1\}$ |

3 | `011` | $\{0,1\}$ |

4 | `100` | $\{2\}$ |

5 | `101` | $\{0,2\}$ |

6 | `110` | $\{1,2\}$ |

7 | `111` | $\{0,1,2\}$ |

With this concept, we can implement our solution.

You'll notice that our code contains some fancy bitwise operations:

`1 << x`

for an integer $x$ is another way of writing $2^x$, which, in binary, has only the $x$'th bit turned on.- The
`&`

(AND) operator will take two integers and return a new integer.`a & b`

for integers $a$ and $b$ will return a new integer whose $i$th bit is turned on if and only if the $i$'th bit is turned on for both $a$ and $b$. Thus,`mask & (1 << x)`

will return a positive value only if the $x$'th bit is turned on in $mask$.

If you wanna learn more about them, we have a dedicated module for bitwise operations.

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {int n;cin >> n;vector<ll> weights(n);for (ll &w : weights) { cin >> w; }

Java

import java.io.*;import java.util.*;public class AppleDivision {public static void main(String[] args) throws Exception {Kattio io = new Kattio();int n = io.nextInt();int[] weights = new int[n];for (int i = 0; i < n; i++) { weights[i] = io.nextInt(); }

Python

n = int(input())weights = list(map(int, input().split()))ans = float("inf")for mask in range(1 << n):sum1 = 0sum2 = 0for i in range(n):# Checks if the ith bit is setif mask & (1 << i):

## Permutations

A **permutation** is a reordering of a list of elements.

Focus Problem – try your best to solve this problem before continuing!

### Lexicographical Order

This term is mentioned quite frequently, ex. in USACO Bronze - Photoshoot.

Think about how are words ordered in a dictionary. (In fact, this is where the term "lexicographical" comes from.)

In dictionaries, you will see that words beginning with the letter `a`

appears
at the very beginning, followed by words beginning with `b`

, and so on. If two
words have the same starting letter, the second letter is used to compare them;
if both the first and second letters are the same, then use the third letter to
compare them, and so on until we either reach a letter that is different, or we
reach the end of some word (in this case, the shorter word goes first).

Permutations can be placed into lexicographical order in almost the same way. We first group permutations by their first element; if the first element of two permutations are equal, then we compare them by the second element; if the second element is also equal, then we compare by the third element, and so on.

For example, the permutations of 3 elements, in lexicographical order, are

Notice that the list starts with permutations beginning with 1 (just like a
dictionary that starts with words beginning with `a`

), followed by those
beginning with 2 and those beginning with 3. Within the same starting element,
the second element is used to make comparisions.

Generally, unless you are specifically asked to find the lexicographically smallest/largest solution, you do not need to worry about whether permutations are being generated in lexicographical order. However, the idea of lexicographical order does appear quite often in programming contest problems, and in a variety of contexts, so it is strongly recommended that you familiarize yourself with its definition.

Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if $N \leq 10$, we can just iterate through all $N!=N\cdot (N-1)\cdot (N-2)\cdots 1$ permutations and check each permutation for validity.

### Solution - Creating Strings I

Resources | ||||
---|---|---|---|---|

CPH | brief explanation + code for both of the methods below |

#### Generating Permutations Recursively

This is just a slight modification of method 1 from CPH.

We'll use the recursive function $\texttt{search}$ to find all the permutations of the string $s$. First, keep track of how many of each character there are in $s$. For each function call, add an available character to the current string, and call $\texttt{search}$ with that string. When the current string has the same size as $s$, we've found a permutation and can add it to the list of $\texttt{perms}$.

C++

#include <bits/stdc++.h>using namespace std;string s;vector<string> perms;int char_count[26];void search(const string &curr = "") {// We've finished creating a permutationif (curr.size() == s.size()) {

Java

import java.io.*;import java.util.*;public class CreatingStrings1 {static String s;static List<String> perms = new ArrayList<String>();static int[] charCount = new int[26];static void search(String curr) {// We've finished creating a permutation

Python

s = input()perms = []char_count = [0] * 26def search(curr: str = ""):# we've finished creating a permutationif len(curr) == len(s):perms.append(curr)return

C++

`next_permutation`

Generating Permutations Using Resources | ||||
---|---|---|---|---|

Mark Nelson | explanation with an example |

Alternatively, we can just use the `next_permutation()`

function. This function
takes in a range and modifies it to the next greater permutation. If there is no
greater permutation, it returns false. To iterate through all permutations,
place it inside a `do-while`

loop. We are using a `do-while`

loop here instead
of a typical `while`

loop because a `while`

loop would modify the smallest
permutation before we got a chance to process it.

What's going to be in the `check`

function depends on the problem, but it should
verify whether the current permutation satisfies the constraints given in the
problem.

do {check(v); // process or check the current permutation for validity} while (next_permutation(v.begin(), v.end()));

Each call to `next_permutation`

makes a constant number of swaps on average if
we go through all $N!$ permutations of size $N$.

### Warning!

One small detail is that you need to sort the string before calling
`next_permutation()`

because the method generates strings in lexicographical
order. If the string isn't sorted, then strings which are lexicographically
smaller than the initial string won't be generated.

#include <bits/stdc++.h>using namespace std;int main() {string s;cin >> s;sort(s.begin(), s.end());// perms is a sorted list of all the permutations of the given string

Java

Python

`itertools.permutations`

Generating Permutations Using Since `itertools.permutations`

treats elements as unique based on position, not
value, it returns all permutations, with repeats. Putting the returned tuples in
a set can filter out duplicates, and since tuples are returned, we need to join
the characters into a string.

from itertools import permutationss = input()# perms is a sorted list of all the permutations of the given stringperms = sorted(set(permutations(s)))print(len(perms))for perm in perms:print("".join(perm))

## Backtracking

Focus Problem – try your best to solve this problem before continuing!

### Resources

Resources | ||||
---|---|---|---|---|

CPH | code and explanation for focus problem | |||

CP2 | iterative vs recursive complete search |

### Solution - Chessboard & Queens

#### By Generating Permutations

A brute-force solution that checks all $\binom{64}{8}$ possible queen combinations will have over 4 billion arrangements to check, making it too slow.

We have to brute-force a bit smarter: notice that we can directly generate permutations so that no two queens are attacking each other due to being in the same row or column.

Since no two queens can be in the same column, it makes sense
to lay one out in each row.
It remains to figure out how to vary the *rows* each queen is in.
This can be done by generating all permutations from $1 \cdots 8$, with the
numbers representing which row each queen is in.

For example, the permutation $[6, 0, 5, 1, 4, 3, 7, 2]$ results in this queen arrangement:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |

0 | Q | |||||||

1 | Q | |||||||

2 | Q | |||||||

3 | Q | |||||||

4 | Q | |||||||

5 | Q | |||||||

6 | Q | |||||||

7 | Q |

Doing this cuts down the number of arrangements we have to check down to a much more managable $8!$.

### Easier Diagonal Checking

To make the implementation easier, notice that some bottom-left to top-right diagonal can be represented as all squares $i, j$ ($i$ being the row and $j$ being the column) such that $i + j = S$ for some $S$. For example, all squares on the diagonal from $6, 0$ to $0, 6$ have their coordinates sum to $6$.

Similarly, some bottom-right to top-left diagonal can be represented as the same thing, but with $i-j$ instead of $i+j$.

C++

#include <bits/stdc++.h>using namespace std;const int DIM = 8;int main() {vector<vector<bool>> blocked(DIM, vector<bool>(DIM));for (int r = 0; r < DIM; r++) {string row;cin >> row;

Java

import java.io.*;import java.util.*;public class ChessboardQueens {private static final int DIM = 8;private static boolean[][] blocked = new boolean[DIM][DIM];private static final List<Integer> queens = new ArrayList<>();private static final boolean[] chosen = new boolean[DIM];

Python

from itertools import permutationsDIM = 8blocked = [[False] * DIM for _ in range(DIM)]for r in range(DIM):row = input()for c in range(DIM):blocked[r][c] = row[c] == "*"

#### Using Backtracking

According to CPH:

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.

Since the bounds are small, we can recursively backtrack over all ways to place the queens, storing the current state of the board.

At each level, we try to place a queen at all squares that aren't blocked or attacked by other queens. After this, we recurse, then remove this queen and backtrack.

Finally, we increment the answer when we've placed all eight queens.

C++

#include <bits/stdc++.h>using namespace std;const int DIM = 8;vector<vector<bool>> blocked(DIM, vector<bool>(DIM));vector<bool> rows_taken(DIM);// Indicators for diagonals that go from the bottom left to the top rightvector<bool> diag1(DIM * 2 - 1);// Indicators for diagonals that go from the bottom right to the top left

Java

import java.io.*;public class ChessboardQueens {private static final int DIM = 8;private static boolean[][] blocked = new boolean[DIM][DIM];private static final boolean[] rowsTaken = new boolean[DIM];// Indicators for diagonals that go from the bottom left to the top rightprivate static final boolean[] diag1 = new boolean[DIM * 2 - 1];

Python

DIM = 8blocked = [[False for _ in range(DIM)] for _ in range(DIM)]for r in range(DIM):row = input()for c in range(DIM):blocked[r][c] = row[c] == "*"rows_taken = [False] * DIM# Indicators for diagonals that go from the bottom left to the top right

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

Bronze | Normal | ## Show TagsComplete Search, Recursion, Subsets | |||

Bronze | Normal | ## Show TagsComplete Search, Permutation, Recursion | |||

Bronze | Normal | ## Show TagsComplete Search, Recursion | |||

CCC | Normal | ## Show TagsComplete Search, Permutation | |||

CF | Hard | ## Show TagsComplete Search, Permutation, Subsets |

You can find more problems at the CP2 link given above or at USACO Training. However, these sorts of problems appear much less frequently than they once did.

Python

For what size of $n$ could we expect a solution that runs through all of the subsets of an array of length $n$ under reasonable time constraints?

Java

For what size of $n$ could we expect a solution that runs through all of the subsets of an array of length $n$ under reasonable time constraints?

C++

What is the time complexity of the following code?

vector<int> perm(n);do {} while (next_permutation(begin(perm), end(perm)));

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!