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:
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);
}