# Section 4. Recursive Backtracking

Section materials curated by Nick Bowman and Kylie Jue, drawing upon materials from previous quarters.

This weekâ€™s section exercises continue our exploration of recursion to tackle even more challenging and interesting problems. In particular, many of 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 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.

``````bool canMakeSumHelper(Vector<int>& v, int target, int cur, int index) {
if (index >= v.size()) {
return cur == target;
}
return canMakeSumHelper(v, target, cur + v[index], index + 1) ||
canMakeSumHelper(v, target, cur, index + 1);
}

bool canMakeSum(Vector<int>& v, int target) {
return canMakeSumHelper(v, target, 0, 0);
}
``````

## 2) Weights and Balances (`weights.cpp`)

Topics: recursive backtracking

I am the only child of parents who weighed,
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 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 right side of the balance. 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`, or
• not get used at all, leaving the target weight on the scale `n`.

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
bool result = isMeasurable(target + last, weights) ||
isMeasurable(target - last, weights) ||
isMeasurable(target, weights);
// un-choose
return result;
}
}
``````

## 3) Change We Can Believe In (`change.cpp`)

Topic: Recursive Backtracking

In the US, as is the case in most countries, the best way to give change for any total is to use a greedy strategy â€“ find the highest-denomination coin thatâ€™s less than the total amount, give one of those coins, and repeat. For example, to pay someone 97Â˘ in the US in cash, the best strategy would be to

• give a half dollar (50Â˘ given, 47Â˘ remain), then
• give a quarter (75Â˘ given, 22Â˘ remain), then
• give a dime (85Â˘ given, 12Â˘ remain), then
• give a dime (95Â˘ given, 2Â˘ remain), then
• give a penny (96Â˘ given, 1Â˘ remain), then
• give another penny (97Â˘ given, 0Â˘ remain).

This uses six total coins, and thereâ€™s no way to use fewer coins to achieve the same total.

However, itâ€™s possible to come up with coin systems where this greedy strategy doesnâ€™t always use the fewest number of coins. For example, in the tiny country of Recursia, the residents have decided to use the denominations 1Â˘, 12Â˘, 14Â˘, and 63Â˘, for some strange reason. So suppose you need to give back 24Â˘ in change. The best way to do this would be to give back two 12Â˘ coins. However, with the greedy strategy of always picking the highest-denomination coin thatâ€™s less than the total, youâ€™d pick a 14Â˘ coin and ten 1Â˘ coins for a total of eleven coins. Thatâ€™s pretty bad!

Your task is to write a function

``````int fewestCoinsFor(int cents, Set<int>& coins)
``````

that takes as input a number of cents and a Set indicating the different denominations of coins used in a country, then returns the minimum number of coins required to make change for that total. In the case of US coins, this should always return the same number as the greedy approach, but in general it might return a lot fewer!

You can assume that the set of coins always contains a 1Â˘ coin, so you never need to worry about the case where itâ€™s simply not possible to make change for some total. You can also assume that there are no coins worth exactly 0Â˘ or a negative number of cents. Finally, you can assume that the number of cents to make change for is nonnegative.

Makes cents? I certainly hope so.

The idea behind this solution is the following: if we need to make change for zero cents, the only (and, therefore, best!) option is to use 0 coins. Otherwise, we need to give back at least one coin. Whatâ€™s the first coin we should hand back? We donâ€™t know which one it is, but we can say that itâ€™s got to be one of the coins from our options and that that coin canâ€™t be worth more than the total. So weâ€™ll try each of those options in turn, see which one ends up requiring the fewest coins for the remainder, then go with that choice. The code for this is really elegant and is shown here:

``````/**
* Given a collection of denominations and an amount to give in change, returns
* the minimum number of coins required to make change for it.
*
* @param cents How many cents we need to give back.
* @param coins The set of coins we can use.
* @return The minimum number of coins needed to make change.
*/
int fewestCoinsFor(int cents, Set<int>& coins) {
/* Base case: You need no coins to give change for no cents. */
if (cents == 0) {
return 0;
}
/* Recursive case: try each possible coin that doesnâ€™t exceed the total as
* as our first coin.
*/
else {
int bestSoFar = cents + 1; // Can never need this many coins;
for (int coin: coins) {
/* If this coin doesnâ€™t exceed the total, try using it. */
if (coin <= cents) {
bestSoFar = min(bestSoFar,
fewestCoinsFor(cents - coin, coins));
}
}
return bestSoFar + 1; // For the coin we just used.
}
}
``````

## 4) Longest Common Subsequence (`lcs.cpp`)

Topic: Recursive Backtracking

Write a recursive function named longestCommonSubsequence that returns the longest common subsequence of two strings passed as arguments. Some example function calls and return values are shown below.

Recall that if a string is a subsequence of another, each of its letters occurs in the longer string in the same order, but not necessarily consecutively.

Hint: In the recursive case, compare the first character of each string. What one recursive call can you make if they are the same? What two recursive calls do you try if they are different?

``````longestCommonSubsequence("cs106a", "cs106b") --> "cs106"
longestCommonSubsequence("nick", "julie") --> "i"
longestCommonSubsequence("karel", "c++") --> ""
longestCommonSubsequence("she sells", "seashells") --> "sesells"
``````
``````string longestCommonSubsequence(string s1, string s2) {
if (s1.length() == 0 || s2.length() == 0) {
return "";
} else if (s1[0] == s2[0]) {
return s1[0] + longestCommonSubsequence(s1.substr(1),
s2.substr(1));
} else {
string choice1 = longestCommonSubsequence(s1, s2.substr(1));
string choice2 = longestCommonSubsequence(s1.substr(1), s2);
if (choice1.length() >= choice2.length()) {
return choice1;
} else {
return choice2;
}
}
}
``````

## 5) Cracking Passwords(`crack.cpp`)

Topic: Recursive Backtracking

Write a function `crack` that takes in the maximum length a site allows for a user's password and tries to find the password into an account by using recursive backtracking to attempt all possible passwords up to that length (inclusive). Assume you have access to the function `bool login(string password)` that returns true if a password is correct. You can also assume that the passwords are entirely alphabetic and case-sensitive. You should return the correct password you find, or the empty string if you cannot find the password. You should return the empty string if the maximum length passed is 0 or throw an integer exception if the length is negative.

Security note: The ease with which computers can brute-force passwords is the reason why login systems usually permit only a certain number of login attempts at a time before timing out. Itâ€™s also why long passwords that contain a variety of different characters are better! Try experimenting with how long it takes to crack longer and more complex passwords. See the comic here for more information: https://xkcd.com/936/

``````string crackHelper(string soFar, int maxLength) {
return soFar;
}
if (soFar.size() == maxLength) {
return "";
}
for (char c = 'a'; c <= 'z'; c++) {
string password = crackHelper (soFar + c, maxLength);
if (password != "") {
}
// Also check uppercase
char upperC = toupper(c);
password = crackHelper (soFar + upperC, maxLength);
if (password != "") {
}
}
return "";
}

string crack(int maxLength) {
if (maxLength < 0) {
throw maxLength;
}
return crackHelper("", maxLength);
}
``````

## 6) The Knapsack Problem (`knapsack.cpp`)

As a challenge problem, we encourage you to explore solving the quintessential optimization challenge of the knapsack problem. As a reminder from lecture, here is the problem setup.

Imagine yourself in a new lifestyle as a professional wilderness survival expert. You are about to set off on a challenging expedition, and you need to pack your knapsack (or backpack) full of supplies. You have a list full of supplies (each of which has a survival value and a weight associated with it) to choose from. Your backpack is only sturdy enough to hold a certain amount of weight. The question is: How can you maximize the survival value of your backpack?

Assume each item in your backpack is modeled with the following struct:

``````struct BackpackItem {
int survivalValue;  // You can assume this value will always >= 0
int weight;         // You can assume this value will always >= 0
};
``````

Your goal is to implement the following function:

``````int fillBackpack(Vector<BackpackItem>& items, int targetWeight);
``````

which given a list of all possible items that you can take with you and the maximum weight that your backpack can hold, returns the maximum survival value that you can achieve by filling the backpack.

``````int fillBackpackHelper(Vector<BackpackItem>& items, int capacityRemaining, int curValue, int index){
/* Base Case: If there is no more capacity in the backpack to hold things,
* then we can no longer fit any more value in.
*/
if (capacityRemaining < 0) {
return 0;
}
/* Base Case: If we have run out of items to consider, then the best value we
* can get is what we've built up so far.
*/
else if (index == items.size()){
return curValue;
}else {
/* Choose: Select an item to decide whether to bring along or not.
*/
BackpackItem curItem = items[index];

/* Explore: Try including the item and not including it, and keep track
* of the best possible value in each case. */
int bestValueWithout = fillBackpackHelper(items,
capacityRemaining,
curValue,
index + 1);

int bestValueWith = fillBackpackHelper(items,
capacityRemaining - curItem.weight,
curValue + curItem.survivalValue,
index + 1);

/* Unchoose: No explicit unchoose necessary since no changes to data
* structures have been made.
*/

/* The final value we return is the best of the two options we tried. */
return max(bestValueWith, bestValueWithout);
}
}

int fillBackpack(Vector<BackpackItem>& items, int targetWeight){
return fillBackpackHelper(items, targetWeight, 0, 0);
}
``````