Rare
0/6

Complete Search with Recursion

Authors: Darren Yao, Sam Zhang, Michael Cao, Andrew Wang

Prerequisites

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 $n\le 20$, we can try all possible divisions of $n$ apples into two sets and find the one with the minimum difference in weights. Here are two ways to do this.

Method 1 - Recursion

Permutations

A permutation is a reordering of a list of elements.

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].$

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.

Generating Permutations

Focus Problem – read through this problem before continuing!

Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if $N \leq 10$, we can probably iterate through all permutations and check each permutation for validity. For a list of $N$ elements, there are $N!$ ways to permute them, and generally we'll need to read through each permutation once to check its validity, for a time complexity of $O(N \cdot N!)$.

Resources
CPHgood explanation + code including next_permutation

C++

About 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.

1do {2    check(v); // process or check the current permutation for validity3} 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$.

Java

Warning!

next_permutation is not available in Java.

Solution - Creating Strings I

Method 1 - Recursively

Method 2 - With next_permutation

Backtracking

Focus Problem – read through this problem before continuing!

Resources
CPH
CP2

Solution - Chessboard & Queens

Method 1 - Generating Permutations

Method 2 - Backtracking

Problems

Warning!

Don't expect a problem like "Grid Paths" in an actual contest.

StatusSourceProblem NameDifficultyTagsSolution
BronzeHardExternal Sol
BronzeHard
Show Tags

permutations

External Sol
CSESInsaneCPH 5.4

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

more probs?