Section3: Recursive Backtracking

Section materials curated by our Head TA Nick Bowman, 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 recurisve 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)

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)

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?

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
		weights.add(last);
		return result;
 	}
}

3) Cracking Passwords (crack.cpp)

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 casesensitive. 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) {
	if (login(soFar)) {
		return soFar;
	}
	if (soFar.size() == maxLength) {
		return "";
	}
	for (char c = 'a'; c <= 'z'; c++) {
		string password = crackHelper (soFar + c, maxLength);
		if (password != "") {
			return password;
		}
 		// Also check uppercase
 		char upperC = toupper(c);
 		password = crackHelper (soFar + upperC, maxLength);
		if (password != "") {
 			return password;
 		}
 	}
	return "";
}

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

4) Longest Common Subsequence (lcs.cpp)

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) Change We Can Believe In (change.cpp)

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 fifteen 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, since that makes no sense. (No pun intended.) Finally, you can assume that the number of cents to make change for is nonnegative.

/**
 * 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.
 	}
}

6) Splitting the bill (bill.cpp)

You’ve gone out for coffees with a bunch of your friends and the waiter has just brought back the bill. How should you pay for it? One option would be to draw straws and have the loser pay for the whole thing. Another option would be to have everyone pay evenly. A third option would be to have everyone pay for just what they ordered. And then there are a ton of other options that we haven’t even listed here!

Your task is to write a function

void listPossiblePayments(int total, Set<string>& people)

that takes as input a total amount of money to pay (in dollars) and a set of all the people who ordered something, then lists off every possible way you could split the bill, assuming everyone pays a whole number of dollars. For example, if the bill was $4 and there were three people at the lunch (call them A, B, and C), your function might list off these options:

A: $4, B: $0, C: $0
A: $3, B: $1, C: $0
A: $3, B: $0, C: $1
A: $2, B: $2, C: $0
A: $2, B: $1, C: $1
A: $2, B: $0, C: $1
…
A: $0, B: $1, C: $3
A: $0, B: $0, C: $4

Some notes on this problem:

• The total amount owed will always be nonnegative. If the total owed is negative, you should use the error() function to report an error.
• There is always at least one person in the set of people. If not, you should report an error.
• You can list off the possible payment options in any order that you’d like. Just don’t list the same option twice.
• The output you produce should indicate which person pays which amount, but aside from that it doesn’t have to exactly match the format listed above. Anything that correctly reports the payment amounts will get the job done.

/*
 * Lists off all ways that the set of people can pay a certain total, assuming
 * that some number of people have already committed to a given set of payments.
 *
 * @param total The total amount to pay.
 * @param people Who needs to pay.
 * @param payments The payments that have been set up so far.
 */
void listPossiblePaymentsRec(int total, Set<string>& people, 
				Map<string, int>& payments) {
	/* Base case: if one person left, they have to pay the whole bill.*/
	if (people.size() == 1) {
		Map<string, int> finalPayments = payments;
		finalPayments[people.first()] = total;
		cout << finalPayments << endl;
	}
	/* Recursive case: The first person has to pay some amount between 0 and 
	* the total amount. Try all of those possibilities.
	*/
	else {
		for (int payment = 0; payment <= total; payment++) {
			/* Create a new assignment of people to payments in which 
			* this first person pays this amount. 
			*/
 			Map<string, int> updatedPayments = payments;
			updatedPayments[people.first()] = payment;
			Set<string> remainingPeople = people - people.first();
			listPossiblePaymentsRec(total - payment, remainingPeople,
						updatedPayments);
		}
	}
}
void listPossiblePayments(int total, Set<string>& people) {
	/* Edge cases: we can't pay a negative total, and there must 
	*  be at least one person.
	*/
 	if (total < 0) error("Guess you're an employee?");
	if (people.isEmpty()) error("Dine and dash?");
	Map<string, int> payments;
	listPossiblePaymentsRec(total, people, payments);
}