PrevNext
Rare
 0/7

Complete Search with Recursion

Authors: Darren Yao, Sam Zhang, Michael Cao, Andrew Wang, Benjamin Qi, Dong Liu

Includes generating subsets and permutations.

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 – read through this problem before continuing!

Resources

Resources
CPHgood explanation + code, no need to repeat

Solution - Apple Division

Since n20n\le 20, we can solve the focus problem by trying all possible divisions of nn 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 weightiweight_i to the first set or the second set, storing two sums s1s_1 and s2s_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;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Java

import java.util.*;
import java.io.*;
public class Main {
static int N;
static int weights[];
public static void main(String[] args) throws Exception {
FastIO sc = new FastIO(System.in); //See "Intro - FastIO" - this class acts similarly to Scanner, but faster

Python

n = int(input())
p = list(map(int, input().split()))
def solve(i, s1, s2):
if i == n:
return abs(s2-s1)
return min(solve(i+1, s1+p[i], s2),
solve(i+1, s1, s2+p[i]))
print(solve(0, 0, 0))

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. For a particular bitmask, if the ii'th bit is turned on (equal to 11), we say the ii'th apple is in s1s_1. Then, the rest of the apples are in s2s_2. We can iterate through all subsets s1s_1 if we check all bitmasks ranging from 00 to 2N12^N-1. For each bitmask, find the sum of s1s_1 and s2s_2 and find the minimum difference between their sums.

Note the fancy bitwise operations:

  • 1 << x for an integer xx is another way of writing 2x2^x, which, in binary, has only the xx'th bit turned on.
  • The & (and) operator will take two integers and return a new integer. a & b for integers aa and bb will return a new integer whose ii'th bit is turned on if and only if the ii'th bit is turned on for both aa and bb. Thus, mask & (1 << x) will return a positive value only if the xx'th bit is turned on in maskmask.

Bitwise Operations

Check the Silver module module for more information.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Java

import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
FastIO sc = new FastIO(System.in); //see "Intro - FastIO" - this class acts similarly to Scanner
PrintWriter pw = new PrintWriter(System.out);
int N = sc.nextInt();
int weights[] = new int[N];

Python

n = int(input())
p = list(map(int, input().split()))
ans = float('inf')
for mask in range(1<<n):
s1,s2 = 0,0
for i in range(n):
if mask & (1<<i):
s1 += p[i]
else:
s2 += p[i]
ans = min(ans, abs(s1-s2))
print(ans)

Permutations

A permutation is a reordering of a list of elements.

Focus Problem – read through 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

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1].[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

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 N10N \leq 10, we can just iterate through all N!=N(N1)(N2)1N!=N\cdot (N-1)\cdot (N-2)\cdots 1 permutations and check each permutation for validity.

Solution - Creating Strings I

Resources
CPHbrief explanation + code for both of the methods below

Generating Permutations Recursively

Just a slight modification of method 1 from CPH.

C++

int N, cnt[26];
str S, perm;
vs perms;
void search() {
if (sz(perm) == sz(S)) {
perms.pb(perm);
return;
}
F0R(i,26) if (cnt[i]) {

Java

import java.util.*;
import java.io.*;
public class Main {
static String s, perm;
static ArrayList<String> perms;
static int N, cnt[];
static void search() {
if (perm.length() == s.length()) {

Generating Permutations Using next_permutation

Resources
Mark Nelsonexplanation 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!N! permutations of size NN.

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.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Java

Warning!

next_permutation is not available in Java.

Backtracking

Focus Problem – read through this problem before continuing!

Resources

Resources
CPHcode and explanation for focus problem
CP2iterative vs recursive complete search

Solution - Chessboard & Queens

Using next_permutation

Since no two queens can be in the same column, let's generate a permutation of length 88. Then, the pip_i represents the column that the ii-th queen goes on.

By generating all permutations, we can quickly test all possible placements, and count how many are valid.

To make the implementation easier, we can observe that some bottom-left to top-right diagonal can be represented as all squares i,ji, j such that i+j=Si + j = S for some SS. Similarly, some bottom-right to top-left diagonal can be represented as i+7ji + 7 - j if i,ji, j are zero-indexed.

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Java

import java.io.*;
import java.util.*;
public class Chessboard {
public static boolean ok[][] = new boolean[8][8];
public static ArrayList < Integer > perm = new ArrayList < Integer > ();
public static boolean[] chosen = new boolean[8];
public static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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.

Then, we can try to place a queen at all squares x,yx, y if it isn't attacked by a queen or blocked and recurse, before removing this queen and backtracking.

Finally, when we have placed all the queens and the board's state is valid, then increment the answer.

C++

string g[8];
bool sum[15], dif[15], c[8];
int ans = 0;
void dfs(int r) { // place queen in r-th row
if (r == 8) {
++ ans; // found valid placement
return;
}
F0R(i,8) if (g[r][i] == '.' && !c[i] && !sum[i+r] && !dif[i-r+7]) {

Java

import java.util.*;
import java.io.*;
public class Main {
static String g[];
static boolean sum[], dif[], c[];
static int ans = 0;
static void dfs(int r) { //place queen in row r
if (r == 8) {
++ ans;

Pruning

Focus Problem – read through this problem before continuing!

Both of the resources below describe this well so I won't repeat it here.

Resources
CPHcode and explanation for focus problem
CP2pruning tips

Problems

None of these require pruning.

StatusSourceProblem NameDifficultyTagsSolutionURL
BronzeHard
Show Tags

permutations

External Sol
BronzeHard
Old BronzeVery Hard
Show Tags

permutations

External Sol

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

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

make code consistent, improve some of these explanations

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!

Give Us Feedback on Complete Search with Recursion!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext