This week’s section exercises continue our exploration of recursion to tackle even more challenging and interesting problems. In particular, this week's section problems center around recursive backtracking, a very powerful and versatile problem solving technique.
Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:
📦 Starter project
1. Win some, lose sum (sum.cpp)
Topics: recursive backtracking
Write a recursive function named canMakeSum that takes a reference to a Vector<int> and an int target value and returns true if it is possible to have some selection of values from the Vector that sum to the target value. In particular, you should be implementing a function with the following declaration
bool canMakeSum(Vector<int>& values, int target)
For example, let's say that we executed the following code
Vector<int> nums = {1,1,2,3,5};
canMakeSum(nums, 9)
We should expect that the call to canMakeSum should return true. Given the values specified in nums, we can select 1, 3, and 5 such that 5 + 3 + 1 = 9.
However, let's say that we executed the following code instead
Vector<int> nums = {1,4,5,6};
canMakeSum(nums, 8);
We should expect that the call to canMakeSum in this case should return false, since there is no possible combination of values from the vector that sum up to the target value of 8.
SOLUTION 1
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar) {
if (v.isEmpty()) {
return sumSoFar == target;
}
/* Here we choose the last element in the vector.
* We could have chosen any element, but the last
* is the easiest and fastest method.
*/
int choice = v[v.size() - 1];
v.remove(v.size() - 1);
bool with = canMakeSumHelper(v, target, sumSoFar + choice);
bool without = canMakeSumHelper(v, target, sumSoFar);
// And then we unchoose, by adding this back!
v.add(choice);
return with || without;
}
bool canMakeSum(Vector<int>& v, int target) {
return canMakeSumHelper(v, target, 0);
}
SOLUTION 2
/*
* This solution is similar to the one above, except it uses
* an additional index parameter in a vector to make the choices,
* instead of removing from the vector like solution 1 did.
*/
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar, int index) {
if (index >= v.size()) {
return sumSoFar == target;
}
// This is our choice now. Remember we can choose any element
// in the vector, so we choose the element at 'index'
int choice = v[index];
bool with = canMakeSumHelper(v, target, sumSoFar + choice, index + 1);
bool without = canMakeSumHelper(v, target, sumSoFar, index + 1);
// We don't have to add back, because we never removed!
return with || without;
}
bool canMakeSum(Vector<int>& v, int target) {
return canMakeSumHelper(v, target, 0, 0);
}
2. Shrink Words (shrink.cpp)
Topics: recursive backtracking
Write a recursive function named shrinkWord that takes a string word and a Lexicon of words, and shrinks the word to the smallest possible word that can be found in the Lexicon. You can think of a the lexicon as a set of all words in the English dictionary. Checkout the documentation for Lexicon to learn more.
string shrinkWord(string input, Lexicon& lex)
The function is best described by this example below:
Given a string "starter", we can shrink it to "a" through these:
starter -> starer (by removing the second t) -> stare (by removing the second r) -> tare (by removing s) -> are (by removing t) -> ae (by removing r) -> a (by removing e). Hence, we'll return "a". Note that all the intermediate words are english words.
As another example, given string "baker", we can shrink it to "bake" through these:
baker -> bake (remove r). We can't shrink any further because if we remove a any another letter, we can't find the resulting word in the lexicon. Hence, we'll return "bake".
Finally, for "fishpond", we can't make a single transformation. So we'll return "fishpond", unchanged.
This is very similar(yes, again!) to the fewest coins problem above. To shrink a word, we'd to remove a letter from the word. The question is, which letter should we remove? This is what our backtracking solution explores!
string shrinkWord(string input, Lexicon& lex) {
// We can't further shrink an empty word.
// Also, if current word we have now is not
// an English word(i.e. it isn't contained in
// the lexicon), that's also invalid(from the problem
// description. )
if (input.empty() || !lex.contains(input)) {
return "";
}
string shortestWord = input;
for (size_t i = 0; i < input.length(); i ++) {
// Remove the letter at index i and recurse!
string subword = input.substr(0, i) + input.substr(i + 1);
string result = shrinkWord(subword, lex);
// Compare the words we've generated so far to
// our shortestWord. If our new word is smaller,
// we have to change our shortestWord!
// We need a special check for the empty string
// because our base case returns "" for invalid inputs.
if (!result.empty() && result.length() < shortestWord.length()) {
shortestWord = result;
}
}
return shortestWord;
}
3. Weights and Balances (weights.cpp)
Topics: Recursive backtracking
measured, and priced everything; for whom
what could not be weighed, measured, and
priced had no existence.
—Charles Dickens, Little Dorrit, 1857
In Dickens’s time, merchants measured many commodities using weights and a two-pan balance – a practice that continues in many parts of the world today. If you are using a limited set of weights, however, you can only measure certain quantities accurately.
For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces, as shown below:
It’s more interesting to discover that you can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as follows below:
Write a recursive function
bool isMeasurable(int target, Vector<int>& weights)
that determines whether it is possible to measure out the desired target amount with a given set of weights, which is stored in the vector weights.
As an example, the function call
Vector<int> weights = {1, 3};
isMeasurable(2, weights);
should return true because it is possible to measure out two ounces using the sample weight set as illustrated in the preceding diagram. On the other hand, calling
Vector<int> weights = {1, 3};
isMeasurable(5, weights);
should return false because it is impossible to use the 1- and 3-ounce weights to add up to 5 ounces. However, the call
Vector<int> weights = {1, 3, 7};
isMeasurable(6, weights);
should return true: you can measure the six-ounce weight by placing it and the one-ounce weight on one side of the scale and by placing the seven-ounce weight on the other.
Here’s a function question to ponder: let’s say that you get to choose n weights. Which ones would you pick to give yourself the best range of weights that you’d be capable of measuring?
Imagine that we start off by putting the amount to be measured (call it n) on the left side of the balance (as shown in the picture on the handout). This makes the target of measurement equal to n. Imagine that there is some way to reach this target n. If we put the weights on the scale one at a time, we can look at where we put that first weight (let’s suppose it weighs w). It must either
- go on the left side, making the target weight on the scale
n + w, - go on the right side, making the target weight on the scale
n - w
We've seen the first two options before, the classic with and without. In this question, there's a third option too:
- not get used at all, leaving the target weight on the scale
n. To see why this is the case, consider a case where you're measuring something weighing 0 ounces. You'd not need any weight to measure 0 ounces so you don't have to put anything on the scale.
If it is indeed truly possible to measure n, then one of these three options has to be the way to do it, even if we don’t know which one it is. The question we then have to ask is whether it’s then possible to measure the new net imbalance using the weights that remain – which we can determine recursively! On the other hand, if it’s not possible to measure n, then no matter which option we choose, we’ll find that there’s no way to use the remaining weights to make everything balanced!
If we’re proceeding recursively, which we are here, we need to think about our base case. There are many options we can choose from. One simple one is the following: imagine that we don’t have any weights at all, that we’re asked to see whether some weight is measurable using no weights. In what circumstances can we do that? Well, if what we’re weighing has a nonzero weight, we can’t possibly measure it – placing it on the scale will tip it to some side, but that doesn’t tell us how much it weighs. On the other hand, if what we’re weighing is completely weightless, then putting it on the scale won’t cause it to tip, convincing us that, indeed, it is weightless! So as our base case, we’ll say that when we’re down to no remaining weights, we can measure n precisely if n = 0. With that in mind, here’s our code:
bool isMeasurable(int target, Vector<int>& weights) {
if (weights.isEmpty()) {
return target == 0; // base case; no weights left to place
} else {
int last = weights[weights.size() - 1]; //using last index is fastest
weights.remove(weights.size() - 1);
// "choose and explore" all of the three possibilities
// This exactly matches the analysis we did above.
bool weightOnLeftSide = isMeasurable(target + last, weights);
bool weightOnRightSide = isMeasurable(target - last, weights);
bool ignoreWeight = isMeasurable(target, weights);
// un-choose
weights.add(last);
// One of these three options will work if we can measure
// the target weight.
return weightOnLeftSide || weightOnRightSide || ignoreWeight;
}
}
4. Domino Tiling (dominoes.cpp)
Topic: Recursive backtracking
Imagine you have a 2 × n grid that you’d like to cover using 2 × 1 dominoes. The dominoes need to be completely contained within the grid (so they can’t hang over the sides), can’t overlap, and have to be at 90° angles (so you can’t have diagonal or tilted tiles). There’s exactly one way to tile a 2 × 1 grid this way, exactly two ways to tile a 2 × 2 grid this way, and exactly three ways to tile a 2 × 3 grid this way (can you see what they are?) Write a recursive function
int numWaysToTile(int n)
that, given a number n, returns the number of ways you can tile a 2 Ă— n grid with 2 Ă— 1 dominoes.
If you draw out a couple of sample tilings, you might notice that every tiling either starts with a single vertical domino or with two horizontal dominoes. That means that the number of ways to tile a 2 × n (for n ≥ 2) is given by the number of ways to tile a 2 × (n – 1) grid (because any of them can be extended into a 2 × n grid by adding a vertical domino) plus the number of ways to tile a 2 × (n – 2) grid (because any of them can be extended into a 2 × n grid by adding two horizontal dominoes). From there the question is how to compute this. You could do this with regular recursion, like this:
int numWaysToTile(int n) {
/* There's one way to tile a 2 x 0 grid: put down no dominoes. */
if (n == 0) return 1;
/* There's one way to tile a 2 x 1 grid: put down a vertical domino. */
if (n == 1) return 1;
/* Recursive case: Use the above insight. */
return numWaysToTile(n - 1) + numWaysToTile(n - 2);
}
5. Compound Words (CompoundWords.cpp)
This question is all about splitting strings apart into smaller, nonempty pieces. To begin, we'd like you to implement a function
Set<Vector<string>> splitsOf(string str);
that takes as input a string, then returns all ways of splitting that string into a sequence of nonempty strings called pieces. For example, given the string "RUBY", you’d return a Set containing these Vector<string>s; notice that all letters are in the same relative order as in the original string:
{"R", "U", "B", "Y"}
{"R", "U", "BY"}
{"R", "UB", "Y"}
{"R", "UBY"}
{"RU", "B", "Y"}
{"RU", "BY"}
{"RUB", "Y"}
{"RUBY"}
If you take any one of these Vectors and glue the pieces together from left to right, you’ll get back the original string "RUBY". Moreover, every possible way of splitting "RUBY" into pieces is included here. Each character from the original string will end up in exactly one piece, and no pieces are empty.
Given the string "TOPAZ", you’d return a Set containing all of these Vector<string>s:
{"T", "O", "P", "A", "Z"}
{"T", "O", "P", "AZ"}
{"T", "O", "PA", "Z"}
{"T", "O", "PAZ"}
{"T", "OP", "A", "Z"}
{"T", "OP", "AZ"}
{"T", "OPA", "Z"}
{"T", "OPAZ"}
{"TO", "P", "A", "Z"}
{"TO", "P", "AZ"}
{"TO", "PA", "Z"}
{"TO", "PAZ"}
{"TOP", "A", "Z"}
{"TOP", "AZ"}
{"TOPA", "Z"}
{"TOPAZ"}
As before, notice that picking one of these Vectors and gluing the pieces in that Vector back together will always give you "TOPAZ".
The decision tree for listing subsets is found by repeatedly considering answers to questions of the form “should I include or exclude this element?” The decision tree for listing permutations is found by repeatedly considering answers to questions of the form “which element should I choose next?” In this problem, the decision tree is found by repeatedly considering answers to this question:
How many characters from the front of the string should I include in the next piece?
i. Decision Tree
Based on this insight, draw the decision tree for listing all splits of the string "JET" along the lines of the decision trees we drew in class. At a minimum, please be sure to do the following:
- Label each entry in the decision tree with the arguments to the recursive call it corresponds to.
- Label each arrow in the decision tree with what choice it corresponds to.
Here's the decision tree for all splits of "JET":
Here, each decision is of the form “how many characters are we taking off the front of the string?,” and we pass down through the recursion both the characters we haven’t used yet and the split we’ve built up so far.
ii. Implement splitsOf
Now, implement the splitsOf function. Your should match the decision tree that you drew in the first part of this problem.
Here’s one implementation of splitsOf based on the above decision tree:
Set<Vector<string>> splitsRec(string str, Vector<string>& chosen) {
/* Base Case: If we've already used up all the characters of the input string,
* then we've already built up one option. The set of all possible options we
* can make given that we're locked into this one solution is just the set of
* that solution by itself.
*/
if (str == "") {
return { chosen };
}
/* Otherwise, there are characters that need to get put into a piece of the
* split. Try all ways of doing this.
*/
else {
Set<Vector<string>> result;
/* Munch off between 1 and all the characters, inclusive. */
for (int i = 1; i <= str.length(); i++) {
string piece = str.substr(0, i);
string remaining = str.substr(i);
/* Find all the splits we can make, assuming we commit to having this
* piece in front.
*/
chosen.add(piece);
result += splitsRec(remaining, chosen);
chosen.remove(chosen.size() - 1);
}
return result;
}
}
Set<Vector<string>> splitsOf(string str) {
Vector<string> chosen = {};
return splitsRec(str, chosen);
}
iii. Implement isCompoundWord
Now that you've gotten a warmup in, let's take aim at a related question. A compound word is an English word like "doorbell" or "heretofore" that can be split apart into multiple English words ("doorbell" becomes "door" and "bell;" "heretofore" becomes "here," "to," and "fore.") Your task is to write a function
bool isCompoundWord(string word, Lexicon& english);
that takes as input a word, then returns whether it's a compound word.
You will likely want to build on the work you've done earlier in this problem. A few things have changed, though. First, you have to split the word apart into multiple pieces. Second, each piece must itself be a word. There are many ways to account for this; explore and see what you find!
Perhaps the trickiest bit here is handling the fact that we have to split into two or more words. There are many ways to do this. Our strategy will be the following. Our recursive logic will completely ignore this requirement, and will be perfectly content to split a string apart into a single word if it feels like it. To force the function to always require at least one word to be munched off, we'll have our wrapper function do an initial splitting step in which it isn't permitted to munch all the characters. Here's what that looks like:
/* Can the given input string be split apart into zero or more English words? */
bool isCompoundRec(string str, Lexicon& english) {
/* Base Case: If the string is empty, we can write it as zero words
* all glued together.
*/
if (str == "") {
return true;
}
/* Recursive Case: Split off some number of characters from the front that
* form a word, then recursively see if what's left is a compound word.
*/
else {
/* Grab between one and all of the characters from the front. */
for (int i = 1; i <= str.length(); i++) {
/* This is a good split if what we've grabbed is a word and the
* remainder is an English word.
*/
if (english.contains(str.substr(0, i)) &&
isCompoundRec(str.substr(i), english)) {
return true;
}
}
/* Oops, nothing works. */
return false;
}
}
bool isCompoundWord(string word, Lexicon& english) {
/* If we aren't a word, then we aren't a compound word. */
if (!english.contains(word)) return false;
/* Otherwise, try pulling off a word from the front and seeing if what's
* left can be made from gluing one or more words together.
*/
for (int i = 1; i < word.length(); i++) {
if (english.contains(word.substr(0, i)) &&
isCompoundRec(word.substr(i), english)) {
return true;
}
}
/* Nope, it's not a compound word, since we tried every option. */
return false;
}