CS106B Recursion and Iteration, Backtracking (2024)

This week’s section exercises explore the ins and outs of content from week 3 – thinking recursively! These problems will help in gaining familiarity with recursive problem-solving.

📦 Starter code

Recursion and Iteration

Problem One: Eating a Chocolate Bar, Take Two

Last week, you explored what it was like to eat a chocolate bar where, at each point in time, you could either eat one square or two. But who are we to tell you how many squares you can eat at once? You're an adult, and you can make your own decisions! If you want to eat five squares at a time, or cram the whole chocolate bar in your mouth in a single bite, go for it!

This increases the number of ways of eating the chocolate bar. For example, here are all the ways to eat a $1 \times 4$ chocolate bar:

  • 1, 1, 1, 1
  • 1, 1, 2
  • 1, 2, 1
  • 1, 3
  • 2, 1, 1
  • 2, 2
  • 3, 1
  • 4

As before, order matters. Last time, we wrote the following function, which counts the number of ways to eat a chocolate bar using bites of sizes 1 and 2.

int numWaysToEat(int numSquares) { /* Can't have a negative number of squares. */ if (numSquares < 0) { error("Negative chocolate? YOU MONSTER!"); } /* If we have zero or one square, there's exactly one way to eat * the chocolate. */ if (numSquares <= 1) { return 1; } /* Otherwise, we either eat one square, leaving numSquares - 1 more * to eat, or we eat two squares, leaving numSquares - 2 to eat. */ else { return numWaysToEat(numSquares - 1) + numWaysToEat(numSquares - 2); }}
  1. Modify this function so that it counts the total number of ways of eating the chocolate bar, not just with bites of size one and two.

    Solution

    In the case where all bites were of size 1 or 2, we fired off two recursive calls. Here, when there's a variable number of recursive calls, we'll use a for loop to try all bite sizes and fire off the recursive call inside the loop.

    int numWaysToEat(int numSquares) { /* Can't have a negative number of squares. */ if (numSquares < 0) { error("Negative chocolate? YOU MONSTER!"); } /* If we have zero squares, there's exactly one way to eat the * chocolate bar, which is to do nothing. */ if (numSquares == 0) { return 1; } /* Otherwise, we will eat somewhere between 1 and numSquares * squares in our next bite. If we eat biteSize pieces off of * the chocolate bar, we'll be left with numSquares - biteSize * pieces remaining. We need to add up all the ways to do this. * Since we don't have a fixed number of recursive calls to * make, we'll use a loop to do this. */ else { int result = 0; for (int biteSize = 1; biteSize <= numSquares; biteSize++) { result += numWaysToEat(numSquares - biteSize); } return result; }}

    Fun fact: this will always print out $2^{\mathtt{numSquares - 1}}$ as its answer, except for when numSquares is zero and it prints $1$. If you're curious why that is, take CS103!

Last time, we wrote the following function to print out all the ways to eat a chocolate bar using bites of size 1 and 2:

/* Print all ways to eat numSquares more squares, given that we've * already taken the bites given in soFar. */void printWaysToEatRec(int numSquares, const Vector<int>& soFar) { /* Base Case: If there are no squares left, the only option is to use * the bites we've taken already in soFar. */ if (numSquares == 0) { cout << soFar << endl; } /* Base Case: If there is one square lfet, the only option is to eat * that square. */ else if (numSquares == 1) { cout << soFar + 1 << endl; } /* Otherwise, we take take bites of size one or of size two. */ else { printWaysToEatRec(numSquares - 1, soFar + 1); printWaysToEatRec(numSquares - 2, soFar + 2); }}void printWaysToEat(int numSquares) { if (numSquares < 0) { error("You owe me some chocolate!"); } /* We begin without having made any bites. */ printWaysToEatRec(numSquares, {});}
  1. Modify this code so that it prints all the ways to eat a chocolate bar with no restrictions on the number of squares per bite.

    Solution

    As above, the major change is a switch from two explicit recursive calls to using a for loop to list off the calls we need to make.

    /* Print all ways to eat numSquares more squares, given that we've * already taken the bites given in soFar. */void printWaysToEatRec(int numSquares, const Vector<int>& soFar) { /* Base Case: If there are no squares left, the only option is to use * the bites we've taken already in soFar. */ if (numSquares == 0) { cout << soFar << endl; } /* Otherwise, try all bite sizes. */ else { for (int biteSize = 1; biteSize <= numSquares; biteSize++) { printWaysToEatRec(numSquares - biteSize, soFar + biteSize); } }}void printWaysToEat(int numSquares) { if (numSquares < 0) { error("You owe me some chocolate!"); } /* We begin without having made any bites. */ printWaysToEatRec(numSquares, {});}

Last time, we wrote this function that returns the a Set of all ways of eating the chocolate bar with bite sizes 1 or 2.

/* Returns all ways to eat numSquares more squares, given that we've * already taken the bites given in soFar. */Set<Vector<int>> waysToEatRec(int numSquares, const Vector<int>& soFar) { /* Base Case: If there are no squares left, the only option is to use * the bites we've taken already in soFar. */ if (numSquares == 0) { /* There is one option here, namely, the set of bites we came up * with in soFar. So if we return all the ways to eat the * chocolate bar given that we've committed to what's in soFar, * we should return a set with just one item, and that one item * should be soFar. */ return { soFar }; } /* Base Case: If there is one square lfet, the only option is to eat * that square. */ else if (numSquares == 1) { /* Take what we have, and extend it by eating one more bite. */ return { soFar + 1 }; } /* Otherwise, we take take bites of size one or of size two. */ else { /* Each individual recursive call returns a set containing the * possibilities that arise from exploring that choice. We want * to combine these together. */ return waysToEatRec(numSquares - 1, soFar + 1) + waysToEatRec(numSquares - 2, soFar + 2); }}Set<Vector<int>> waysToEat(int numSquares) { if (numSquares < 0) { error("You owe me some chocolate!"); } /* We begin without having made any bites. */ return waysToEatRec(numSquares, {});}
  1. Modify this function to allow bites of any sizes, not just 1 and 2.

    Solution

    This will feel like a mix between the first two approaches. In the first approach, we had to declare a local variable to track the sum from across all the recursive calls. In the second approach, we passed extra information down at each step to track what choices we've made so far. Particle acceleratoring them together gives this solution:

    /* Returns all ways to eat numSquares more squares, given that we've * already taken the bites given in soFar. */Set<Vector<int>> waysToEatRec(int numSquares, const Vector<int>& soFar) { /* Base Case: If there are no squares left, the only option is to use * the bites we've taken already in soFar. */ if (numSquares == 0) { /* There is one option here, namely, the set of bites we came up * with in soFar. So if we return all the ways to eat the * chocolate bar given that we've committed to what's in soFar, * we should return a set with just one item, and that one item * should be soFar. */ return { soFar }; } /* Otherwise, we have to take a bite. Try all sizes. */ else { Set<Vector<int>> result; for (int biteSize = 1; biteSize <= numSquares; biteSize++) { result += waysToEatRec(numSquares - biteSize, soFar + biteSize); } return result; }}Set<Vector<int>> waysToEat(int numSquares) { if (numSquares < 0) { error("You owe me some chocolate!"); } /* We begin without having made any bites. */ return waysToEatRec(numSquares, {});}

Problem Two: Tricky Recursion Tracing

Topics: Recursion call and return, Tracing

Below is a recursive functions along with an initial call to that functions. Determine what value is returned from the function. As a note, the function contains a bug (or at least, highly misleading code) that makes it not behave in the way you might initially expect. In addition to tracing the function, make a note of what specifically that function does that's Cruel and Unusual.

int batken(const Vector<int>& v) { if (v.isEmpty()) { return -1; } int total = 0; for (int i = 1; i < v.size(); i++) { total += v[i]; return batken(v.subList(i)); } return total;}// Determine what this outputs!cout << batken({1, 2, 3, 4}) << endl;

Solution

An important detail to notice in this function is that there’s something broken with how the for loop works: the for loop can never execute more than once. That’s because the last line of the for loop is a return statement, and a return statement ends the current function call. As a result, here’s what happens:

  • batken({1, 2, 3, 4}) returns the value of batken({2, 3, 4})
  • batken({2, 3, 4}) returns the value of batken({3, 4})
  • batken({3, 4}) returns the value of batken({4})
  • batken({4}) skips the for loop because the initial value of i is equal to the size of the vector, so then it proceeds to return 0.

Therefore, the return value is zero.

This leads to this piece of advice:

It is exceedingly rare in any context, and in particular in the context of recursion, to have a for loop that ends with an unconditional return statement.

Optimization and Enumeration

Problem Three: Splitting The Bill

Topic: Recursion, Combinations, Sets

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

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.

Solution

The insight that we used in our solution is that the first person has to pay some amount of money. We can't say for certain how much it will be, but we know that it's going to have some amount of money that's between zero and the full total. We can then try out every possible way of having them pay that amount of money, which always leaves the remaining people to split up the part of the bill that the first person hasn't paid.

/** * 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, const Set<string>& people, const Map<string, int>& payments) { /* Base case: if there's 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; listPossiblePaymentsRec(total - payment, people - people.first(), updatedPayments); } }}void listPossiblePayments(int total, const 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?"); listPossiblePaymentsRec(total, people, {});}

Problem Four: Avoiding Sampling Bias

One of the risks that comes up when conducting field surveys is sampling bias, that you accidentally survey a bunch of people with similar backgrounds, tastes, and life experiences and therefore end up with a highly skewed view of what people think, like, and feel. There are a number of ways to try to control for this. One option that’s viable given online social networks is to find a group of people of which no two are Facebook friends, then administer the survey to them. Since two people who are a part of some similar organization or group are likely to be Facebook friends, this way of sampling people ensures that you geta fairly wide distribution.

For example, in the social network shown below (with lines representing friendships), the folks shaded in gray would be an unbiased group, as no two of them are friends of one another.

CS106B Recursion and Iteration, Backtracking (1)

Your task is to write a function

Set<string> largestUnbiasedGroupIn(const Map<string, Set<string>>& network);

that takes as input a Map representing Facebook friendships (described later) and returns the largest group of people you can survey, subject to the restriction that you can’t survey any two people who are friends.

The network parameter represents the social network. Each key is a person, and each person’s associ-ated value is the set of all the people they’re Facebook friends with. You can assume that friendship issymmetric, so if person A is a friend of person B, then person B is a friend of person A. Similarly, you can assume that no one is friends with themselves.

Something to keep in mind: Your solution must not work by simply generating all possible groups of people and then checking at the end which ones are valid (i.e. whether no two people in the group are Facebook friends). This approach is far too slow to be practical.

Solution

One way to solve this problem is to focus on a single person. If we choose this person, we’d want to pick, from the people who aren’t friends with that person, the greatest number of people that we can. If we exclude this person, we’d like to pick from the remaining people the greatest number of people that we can. One of those two options must be optimal, and it’s just a question of seeing which one’s better.

/** * Given a network and a group of permitted people to pick, returns the largest * group you can pick subject to the constraint that you only pick people that * are in the permitted group. * * @param network The social network. * @param permissible Which people you can pick. * @return The largest unbiased group that can be formed from those people. */Set<string> largestGroupInRec(const Map<string, Set<string>>& network, const Set<string>& permissible) { /* Base case: If you aren’t allowed to pick anyone, the biggest group you * can choose has no people in it. */ if (permissible.isEmpty()) return {}; /* Recursive case: Pick a person and consider what happens if we do or do not * include them. */ string next = permissible.first(); /* If we exclude this person, pick the biggest group we can from the set of * everyone except that person. */ auto without = largestGroupInRec(network, permissible - next); /* If we include this person, pick the biggest group we can from the set of * people who aren’t them and aren’t one of their friends, then add the * initial person back in. */ auto with = largestGroupInRec(network, permissible - next - network[next]) + next; /* Return the better of the two options. This uses the ternary conditional * operator ?:. The expression expr? x : y means "if expr is true, then * evaluate to x, and otherwise evaluate to y." */ return with.size() > without.size()? with : without;}Set<string> largestUnbiasedGroupIn(const Map<string, Set<string>>& network) { Set<string> everyone; for (string person: network) { everyone += person; } return largestGroupInRec(network, everyone);}

Problem Five: Social Distancing, C++ Edition

There’s a checkout line at a local grocery store. It’s one meter wide, some number of meters long, and subdivided into one-meter-by-one-meter squares. Each of those squares is either empty or has a person standing in it. We can represent the state of the checkout line as a string made of the characters 'P' and '.', where 'P' represents a square with a person in it and '.' represents a square with no one in it.

Social distancing rules require there to be at least two meters of empty space between each pair of people. So, for example, the string:

P..P....P........P

has everyone obeying social distancing rules, while the string

P..P..P.P

does not. Similarly, the string

P..P....PP....P

does not obey social distancing rules.

Your task is to write a function

Set<string> safeArrangementsOf(int lineLength, int numPeople);

that takes as input the length of the line (in meters) and the number of people in the line, then returns all arrangements of the checkout line that maintain the social distancing requirements. For example, calling safeArrangementsOf(12, 4) would return these strings:

P..P..P..P..P..P..P...P.P..P..P....PP..P...P..P.P..P...P...PP..P....P..PP...P..P..P.P...P..P...PP...P...P..PP....P..P..P.P..P..P..P..P..P..P...P.P..P...P..P.P...P..P..P..P..P..P..P

On the other hand, calling safeArrangementsOf(8, 4) would return an empty set, since there’s no way to fit four people into a line eight meters long while ensuring everyone is at least two meters apart. (Do you see why?)

Solution

There are many ways to solve this problem. These first two solutions are based on the following insight. We're going to build the line from the left to the right, and the recursive calls will progressively reduce the remaining size of the line until all squares in the line have been filled in. At each point, we have two choices:

  • We can build another blank square. (You could optionally restrict this to say "we can build another blank square provided that we have enough space to fit everyone else," which will speed things up a bit but isn't strictly necessary given the problem statement.)
  • We can place a person - provided that there are people left to place and provided that this doesn't conflict with the previously-placed person.

At the end, we'll have our line of people. Provided that we placed everyone, we can use that way of filling in the line as one of our generated strings. But if we reach the end of the line and haven't placed everyone - or if there's no possible way to fit everyone in - we can stop looking and say that no solution exists down this branch.

Here are two ways of implementing this solution. This first one uses the endsWith function, as suggested in the problem statement:

/* Given a target line length, a remaining number of people, and the line we've * assembled so far, produce a set of all ways of filling in the rest of the * line to fit that many people. */Set<string> safeArrangementsRec(int lineLength, int numPeople, const string& soFar) { /* Base case: The line has reached its full length. */ if (soFar.length() == lineLength) { /* Did we place everyone? If so, great! This is a solution. */ if (numPeople == 0) { return { soFar }; } /* Oops, we didn't fit everyone. There are no ways to extend this line * into one that fits everyone. */ else { return {}; } } /* We can always lay down another empty spot. We could (should?) check to * make sure that doing so doesn't leave the remainder of the line in a * state where the remaining people can't be placed, but didn't do that * here. */ Set<string> result = safeArrangementsRec(lineLength, numPeople, soFar + "."); /* We can sometimes lay down a person. Specifically, there has to be at * least one person remaining, and the line can't end with a person or * with a person two steps back. */ if (numPeople > 0 && !endsWith(soFar, "P") && !endsWith(soFar, "P.")) { /* One fewer person needs to be placed. */ result += safeArrangementsRec(lineLength, numPeople - 1, soFar + "P"); } return result;}Set<string> safeArrangementsOf(int lineLength, int numPeople) { return safeArrangementsRec(lineLength, numPeople, "");}

This second solution instead includes an extra parameter indicating how far back you have to look to find the most recent person. Aside from that, the core recursive structure is the same.

/* Given a target line length, a remaining number of people, a partial line, and * how far back in the line we have to look to find the most recent person, * return a set of all ways to extend the line to hold the appropriate number of * people. */Set<string> safeArrangementsRec(int lineLength, int numPeople, const string& soFar, int distance) { /* Base case: The line has reached its full length. */ if (soFar.length() == lineLength) { /* Did we place everyone? If so, great! This is a solution. */ if (numPeople == 0) { return { soFar }; } /* Oops, we didn't fit everyone. There are no ways to extend this line * into one that fits everyone. */ else { return {}; } } /* We can always lay down another empty spot. We could (should?) check to * make sure that doing so doesn't leave the remainder of the line in a * state where the remaining people can't be placed, but didn't do that * here. * * Notice that the distance increases here, since we are now one step * further away from the previous person. */ Set<string> result = safeArrangementsRec(lineLength, numPeople, soFar + ".", distance + 1); /* We can sometimes lay down a person. Specifically, do that if there is at * least one person left and we're at least two steps away from the last * person. */ if (numPeople > 0 && distance >= 2) { /* Distance in this recursive call resets to zero, since there's a * person right at the end. */ result += safeArrangementsRec(lineLength, numPeople - 1, soFar + "P", 0); } return result;}Set<string> safeArrangementsOf(int lineLength, int numPeople) { /* At the beginning, there's no restriction on where the first person can go, * so we pretend we're really far away from the last person. */ return safeArrangementsRec(lineLength, numPeople, "", 2);}

Here's a solution based on a different insight. Like the above solutions, this one works by either placing down a blank spot or placing down a person. However, when placing down a person, we consider two options:

  • That person is the last person in the list. In that case, they can go anywhere in the remainder of the list, and so we'll consider all ways of placing them down that way.
  • That person is not the last person in the list. In that case, we place down the person, plus two blank spaces, to ensure adequate separation between them and the next person.

This approach needs to make sure not to exceed the maximum space allowed in the line. There are many ways to do this, and our approach works by ensuring that there's adequate space to place everyone, stopping as soon as we're out of room.

/* Given the amount of remaining space in the line and the number of remaining * people in the line, produce a set of all possible ways of completing the * partial line provided into a valid socially-distanced arrangement. */Set<string> safeArrangementsRec(int lineLength, int numPeople, const string& soFar) { /* Base case: If you can't fit everyone remaining in the line, then there * is no way to extend what we have. * * The calculation shown here is derived from the insight that, with n * people, you need at least enough space to hold the pattern P..P..P..P, * n times. Here, (n-1) of the people take up three spots, and the last * person takes up one spot. * * This also works in the case where there are zero people. The formula * says we need at least -1 spots to hold zero people, and it's indeed true * that every line with at least -1 spots remaining can hold zero more * people. */ if (3 * (numPeople - 1) + 1 > lineLength) { return { }; // Impossible. } /* Base case: If there are no people left, then the rest of the line has to * be empty. */ if (numPeople == 0) { string result = soFar; for (int i = 0; i < lineLength; i++) { result += "."; } return { result }; } /* Base case: If there is just one person left, they can fill any of the * remaining spots in the line. This case is different from the others * because we do not have any restrictions on how many dots can come after * this person. */ if (numPeople == 1) { Set<string> result; /* Try all places where the person can go. */ for (int pSpot = 0; pSpot < lineLength; pSpot++) { string soln = soFar; /* Append a tail to the line with the person at index pSpot. */ for (int i = 0; i < lineLength; i++) { if (i == pSpot) soln += "P"; else soln += "."; } result += soln; } return result; } /* Recursive case: The next spot may either be empty or have the next person * in it. If it's empty, we have one fewer place left to put people. If it's * full, place down the person and two spaces, reducing the available room * by three. */ return safeArrangementsRec(lineLength - 1, numPeople, soFar + ".") + safeArrangementsRec(lineLength - 3, numPeople - 1, soFar + "P..");}Set<string> safeArrangementsOf(int lineLength, int numPeople) { return safeArrangementsRec(lineLength, numPeople, "");}

Here's the last of the major solution routes we know of. This approach works based on the following insight. If we need to place a person down, there needs to be some number of blank spots before we see that person. We loop over all possible choices for how many blank spots we put down before we put down that person and try each option to see what we find. This basically takes what some of the above approaches are doing and shuffles around how the recursive calls work. Instead of branching with "place a person" or "don't," we only consider the "place a person" option, then decide how many "or don'ts" we're going to do all at once. This strategy can be combined with several of the above ideas to produce different variants; here's the one we think is easiest, which works by including an extra parameter indicating how much space we need to leave between us and the previous person (which is zero for the first person and two for everyone else.)

/* Given the remaining amount of space, the remaining number of people, the line * we've built up thus far, and how much separation we need to enforce between the * next person and the previous person, produce all ways of extending the current * line into one that holds everyone. */Set<string> safeArrangementsRec(int lineLength, int numPeople, const string& soFar, int minDistance) { /* Base case: No people left? Then pad the rest of the string and * we're done! */ if (numPeople == 0) { string result = soFar; for (int i = 0; i < lineLength; i++) { result += '.'; } return { result }; } /* Base case: No space left? Since there's someone left, we are out of * options and nothing will work. */ if (lineLength == 0) { return {}; } /* Recursive case: The next person must go somewhere. Where do we put * them? Try all options and see what we find. */ /* Prefix of dots to separate us from the previous person. */ string prefix; for (int i = 0; i < minDistance; i++) { prefix += '.'; } /* Keep expanding our prefix until we've tried all options. */ Set<string> result; while (prefix.length() < lineLength) { /* We use up the prefix space, plus space for the next person, and need * to keep at least two units of space betwen the next person and this * one. */ result += safeArrangementsRec(lineLength - prefix.length() - 1, numPeople - 1, soFar + prefix + 'P', 2); /* Expand the prefix. */ prefix += '.'; } return result;}Set<string> safeArrangementsOf(int lineLength, int numPeople) { return safeArrangementsRec(lineLength, numPeople, "", 0);}

Problem Six: Change We Can Believe In

Topics: Sets, Recursion, Optimization

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, const Set<int>& coins);

that takes as input a number of cents and a Set<int> 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!

And here’s a question to ponder: given a group of coins, how would you determine whether the greedy algorithm is always optimal for those coins?

It's possible that you won't be able to make the total. For example, if you're asked to make 1¢ and only have 2¢ coins, there's no way to make the total. In that case, return cents + 1 as a sentinel value. This number is bigger than any amount that could actually be needed, and therefore signals to the user that the total can't be made. On the other hand, if the input is illegal (say, asking for change for a negative number of cents), you should call error to report an error.

Once you've got things working, add memoization into your solution to speed things up.

Solution

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 pay some amount. To do that, we'll pick one of our coins - it doesn't matter which - and ask how many times we're going to use that coin. That will be some number between 0 and the amount to pay divided by the value of that coin. We'll recursively explore each of these options, recording which one gives us the best result.

Here's what that might look like.

int fewestCoinsFor(int cents, const Set<int>& coins) { /* Can't have a negative number of cents. */ if (cents < 0) { error("You owe me money, not the other way around!"); } /* Base case: You need no coins to give change for no cents. */ else if (cents == 0) { return 0; } /* Base case: No coins exist. Then it's not possible to make the * amount. In that case, give back a really large value as a * sentinel. */ else if (coins.isEmpty()) { return cents + 1; } /* Recursive case: Pick a coin, then try using each distinct number of * copies of it that we can. */ else { /* The best we've found so far. We initialize this to a large value so * that it's replaced on the first iteration of the loop. Do you see * why cents + 1 is a good choice? */ int bestSoFar = cents + 1; /* Pick a coin. */ int coin = coins.first(); /* Try all amounts of it. */ for (int copies = 0; copies * coin <= cents; copies++) { /* See what happens if we make this choice. Once we use this * coin, we won't use the same coin again in the future. */ int thisChoice = copies + fewestCoinsFor(cents - copies * coin, coins - coin); /* Is this better than what we have so far? */ if (thisChoice < bestSoFar) { bestSoFar = thisChoice; } } /* Return whatever worked best. */ return bestSoFar; }}

Now, let's talk memoization, because this code could really benefit from it! We will regularly be asked to make change for the same combination of a total cent value and mix of coins. For example, using five pennies and no nickels, or zero pennies and one nickel, will both require us to make change for 5 cents less than the total we started with, having already used pennies and nickels.

For memoization to work correctly, we'll need a table that maps the input to the recursive call to the result of that recursive call. In our case, that might seem hard. Our input here consists of a combination of a number of cents (an int) and a set of coins (a Set<int>). However, with a bit of creativity, we can make this work.

The first observation we need is that the exact order in which we try out the different coins is up to us. We can therefore make a Vector<int> containing the coin denominations. This lets us talk about the first coin, the second coin, the third coin, etc. We can then ask how many copies of the first coin we want, then the second, then the third, etc. If we rewrite things this way, here's what we get:

/* How few coins are needed to make the total, given that we can only use * coins from index startIndex and onward? */int fewestCoinsRec(int cents, const Vector<int>& coins, int startIndex) { /* Can't have a negative number of cents. */ if (cents < 0) { error("You owe me money, not the other way around!"); } /* Base case: You need no coins to give change for no cents. */ else if (cents == 0) { return 0; } /* Base case: No coins exist. Then it's not possible to make the * amount. In that case, give back a really large value as a * sentinel. */ else if (startIndex == coins.size()) { return cents + 1; } /* Recursive case: Pick a coin, then try using each distinct number of * copies of it that we can. */ else { /* The best we've found so far. We initialize this to a large value so * that it's replaced on the first iteration of the loop. Do you see * why cents + 1 is a good choice? */ int bestSoFar = cents + 1; /* Pick a coin. */ int coin = coins[startIndex]; /* Try all amounts of it. */ for (int copies = 0; copies * coin <= cents; copies++) { /* See what happens if we make this choice. Once we use this * coin, we won't use the same coin again in the future. */ int thisChoice = copies + fewestCoinsRec(cents - copies * coin, coins, startIndex + 1); /* Is this better than what we have so far? */ if (thisChoice < bestSoFar) { bestSoFar = thisChoice; } } /* Return whatever worked best. */ return bestSoFar; }}int fewestCoinsFor(int cents, const Set<int>& coins) { /* Convert from a Set<int> to a Vector<int> so we have a nice ordering * on things. */ Vector<int> coinVec; for (int coin: coins) { coinVec += coin; } /* Now ask how many coins are needed to make the total, using any coins * from index 0 onward. */ return fewestCoinsRec(cents, coinVec, 0);}

Now, we can notice that the only things that change in our inputs are the number of cents left and the index at which we're looking in the vector. Those are two int values, so we can think of our memoization table as a Grid<int>. Rows correspond to cents left, and columns correspond to start indices.

Here's what this looks like with memoization factored in:

/* How few coins are needed to make the total, given that we can only use * coins from index startIndex and onward? */int fewestCoinsRec(int cents, const Vector<int>& coins, int startIndex, Grid<int>& memo) { /* Base case: You need no coins to give change for no cents. */ if (cents == 0) { return 0; } /* Base case: No coins exist. Then it's not possible to make the * amount. In that case, give back a really large value as a * sentinel. */ else if (startIndex == coins.size()) { return cents + 1; } /* Base case: We already know the answer. */ else if (memo[cents][startIndex] != -1) { return memo[cents][startIndex]; } /* Recursive case: Pick a coin, then try using each distinct number of * copies of it that we can. */ else { /* The best we've found so far. We initialize this to a large value so * that it's replaced on the first iteration of the loop. Do you see * why cents + 1 is a good choice? */ int bestSoFar = cents + 1; /* Pick a coin. */ int coin = coins[startIndex]; /* Try all amounts of it. */ for (int copies = 0; copies * coin <= cents; copies++) { /* See what happens if we make this choice. Once we use this * coin, we won't use the same coin again in the future. */ int thisChoice = copies + fewestCoinsRec(cents - copies * coin, coins, startIndex + 1, memo); /* Is this better than what we have so far? */ if (thisChoice < bestSoFar) { bestSoFar = thisChoice; } } /* Return whatever worked best. */ memo[cents][startIndex] = bestSoFar; return bestSoFar; }}int fewestCoinsFor(int cents, const Set<int>& coins) { /* Can't have a negative number of cents. */ if (cents < 0) { error("You owe me money, not the other way around!"); } /* Convert from a Set<int> to a Vector<int> so we have a nice ordering * on things. */ Vector<int> coinVec; for (int coin: coins) { coinVec += coin; } /* Build our memoization table. Since the number of cents left ranges from * 0 to cents, we need cents+1 rows. Since the start index of the coin * ranges from 0 to coins.size(), we make coins.size() + 1 columns. * * -1 is used as a sentinel to indicate "nothing has been computed here * yet." */ Grid<int> memo(cents + 1, coins.size() + 1, -1); /* Now ask how many coins are needed to make the total, using any coins * from index 0 onward. */ return fewestCoinsRec(cents, coinVec, 0, memo);}

Recursive Backtracking

Problem Seven: Win Sum, Lose Sum

In this problem, you'll walk through a series of steps to build up a recursive backtracking solution to a classic problem in theoretical computer science.

You are given a Set<int> containing some integers. By adding up different groups of numbers from that Set, you can form different sums. For example, given the set {1, 2, 5, 9}, you can form these sums:

  • You could add up no values to get 0.
  • You could add 1 + 2 to get 3.
  • You could add 1 + 5 to get 6.
  • You could add up 1 by itself to get 1.
  • (etc.)

With the set given above, it's not possible to pick numbers that add up to $4$, but it is possible to pick numbers that add up to $5$, $6$, $7$, $8$, $9$, $10$, $11$, and $12$. You can't make $13$, but you can make $14$, $15$, and $16$.

  1. Write a function

    Set<int> numbersMadeFrom(const Set<int>& values);

    that takes as input a Set<int> of numbers, then returns a Set<int> containing all the numbers that can be made by summing up zero or more values from values.

    Solution

    You might recognize that this feels a lot like subsets - for each number, we can either include that number or exclude that number. All we need to do is keep track of what we come up with at each point.

    /* What numbers can we make by adding elements from values, given that our * current total is totalSoFar? */Set<int> numbersMadeFromRec(const Set<int>& values, int totalSoFar) { /* Base Case: No numbers left? We can make totalSoFar, and nothing * else. */ if (values.isEmpty()) { return { totalSoFar }; } /* Recursive Case: Pick an element from the set. We either include it * or exclude it. Try both options and see what we find. */ else { int number = values.first(); return numbersMadeFromRec(values - number, totalSoFar) + // Exclude it numbersMadeFromRec(values - number, totalSoFar + number); // Include it }}Set<int> numbersMadeFrom(const Set<int>& values) { return numbersMadeFromRec(values, 0);}

Now, suppose that you're interested not in finding every number you can make, but rather determining whether it's possible to make a particular number called the target number. You could in principle solve this by using your solution from before - generate every number you can make, then check if your target number is in there. However, that wouldn't be a good idea for two reasons:

  1. The Set returned from this function can be enormous. For example, if you have a 30-element input set, you can have up to $2^{30} \approx 1,000,000,000$ elements in the resulting set! If you only care about one of them, it's wasteful to produce so many other numbers.
  2. Suppose that your recursion, early on, figures out how to make the target number. In that case, any additional work being done by the function is wasteful, since you're generating numbers you don't need.

To address this, we'll need to change the function so that it doesn't report all the numbers it finds and instead stops as soon as it finds one that works.

  1. Using your previous function as a starting point, write a function

    bool canMakeTarget(const Set<int>& values, int target);

    that takes as input a Set<int> and a target number, then returns whether you can add up some collection of the numbers in value to get target.

    Solution

    In many ways, this function is going to work similarly to the previous one. We'll keep track of what we've added up so far, and at each point will either include or exclude the next item from the set. Unlike last time, though, the way in which we'll combine values together will not be by adding them, and we'll need another base case to account for the possibiltiy that we've already hit our total. Here's what that looks like:

    /* Can we make the value target with the numbers remaining from values, * given that our current sum is target? */bool canMakeTargetRec(const Set<int>& values, int target, int totalSoFar) { /* Base Case 1: If we hit the target, we're done! */ if (totalSoFar == target) { return true; } /* Base Case 2: Otherwise, if there are no numbers left in the set, we * know that we can't make the target given the decisions we have * committed to so far. */ else if (values.isEmpty()) { return false; } /* Recursive Case: Pick an element from the set. We either include it * or exclude it. Try both options and see what we find. */ else { int number = values.first(); /* We use the OR (||) operator here, since if either option leads to * our total then we can make it, and if neither option leads to our * total we know we can't make the total given the decisions we've * committed to at this point. */ return canMakeTargetRec(values - number, target, totalSoFar) || // Exclude it canMakeTargetRec(values - number, target, totalSoFar + number); // Include it }}bool canMakeTarget(const Set<int>& values, int target) { return canMakeTargetRec(values, target, 0);}

    As a note, you can combine the two parameters target and totalSoFar together in canMakeTarget. Instead of adding values to totalSoFar, subtract them from target, and stop once target is zero.

You now have a function that will tell you whether it's possible to sum numbers up to reach a target. However, when the function finishes running, all you'll have is the bool saying "yes, it's possible" or "no, it isn't." But what if it is possible, and you'd like to know one way to get the values to add up to the target?

  1. Modify your canMakeTarget function so that it has this signature:

    bool canMakeTarget(const Set<int>& values, int target, Set<int>& solution);

    Your function should, as before, take in values and target and see whether it's possible to find numbers in values that sum up to target. If not, your function should return false. But if it is possible, your function should return true and then modify solution so hold one subset of values that adds up to target.

    Solution

    There are several different ways to do this.

    This first approach works by replacing the integer totalSoFar with a Set<int> consisting of the choices that we have made up to this point. If we find that it adds up to exactly target, great! We can overwrite solution with that as our answer.

    /* Helper function to add up the integers in a set. */int sumOf(const Set<int>& values) { int result = 0; for (int value: values) { result += value; } return result;}/* Can we make the value target with the numbers remaining from values, * given that our current sum is target? */bool canMakeTargetRec(const Set<int>& values, int target, const Set<int>& soFar, Set<int>& solution) { /* Base Case 1: If we hit the target, we're done! */ if (sumOf(soFar) == target) { solution = soFar; // Write down the solution return true; } /* Base Case 2: Otherwise, if there are no numbers left in the set, we * know that we can't make the target given the decisions we have * committed to so far. */ else if (values.isEmpty()) { return false; } /* Recursive Case: Pick an element from the set. We either include it * or exclude it. Try both options and see what we find. */ else { int number = values.first(); /* We use the OR (||) operator here, since if either option leads to * our total then we can make it, and if neither option leads to our * total we know we can't make the total given the decisions we've * committed to at this point. */ return canMakeTargetRec(values - number, target, soFar, solution) || // Exclude it canMakeTargetRec(values - number, target, soFar + number, solution); // Include it }}bool canMakeTarget(const Set<int>& values, int target, Set<int>& solution) { return canMakeTargetRec(values, target, {}, solution);}

    Another option is to not pass down a set like that and to instead use our old approach of having the sum of the numbers we've seen so far. Then, as the recursion unwinds when we find a successful option, we can add in the number if we used it. Here's what this might look like:

    /* Can we make the value target with the numbers remaining from values, * given that our current sum is target? */bool canMakeTargetRec(const Set<int>& values, int target, int totalSoFar, Set<int>& solution) { /* Base Case 1: If we hit the target, we're done! */ if (totalSoFar == target) { /* Clear out whatever happened to be in solution up to this point. */ solution = {}; return true; } /* Base Case 2: Otherwise, if there are no numbers left in the set, we * know that we can't make the target given the decisions we have * committed to so far. */ else if (values.isEmpty()) { return false; } /* Recursive Case: Pick an element from the set. We either include it * or exclude it. Try both options and see what we find. */ else { int number = values.first(); /* First, see what happens if we exclude the number. */ if (canMakeTargetRec(values - number, target, totalSoFar, solution)) { /* Great, a solution exists! We haven't included anything here, so * whatever that solution is doesn't need number in it. */ return true; } /* Now try including the number. */ if (canMakeTargetRec(values - number, target, totalSoFar + number, solution)) { /* A solution exists assuming we add in number. So let's add number * into the solution that was found. */ solution += number; return true; } /* Oh fiddlesticks, neither works. */ return false; }}bool canMakeTarget(const Set<int>& values, int target, Set<int>& solution) { return canMakeTargetRec(values, target, 0, solution);}

Problem Eight: Weights and Balances

Thanks to Eric Roberts for this problem

Topics: Recursion, Combinations, 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:

CS106B Recursion and Iteration, Backtracking (2)

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:

CS106B Recursion and Iteration, Backtracking (3)

Write a recursive function,

bool isMeasurable(int target, const 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

isMeasurable(2, { 1, 3 })

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

isMeasurable(5, { 1, 3 })

should return false because it is impossible to use the 1- and 3-ounce weights to add up to 5 ounces. However, the call

isMeasurable(6, { 1, 3, 7 })

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?

Solution

Imagine that we start off by putting the amount to be measured (call it n) on the left side of the balance. This makes the imbalance on the scale equal to n. Imagine that there is some way to measure 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 net imbalance on the scale n + w, or
  • go on the right side, making the net imbalance on the scale n – w, or
  • not get used at all, leaving the net imbalance 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:

/** * Given an amount, a list of weights, and an index, determines whether it's * possible to measure n using the weights at or after the index given by * startPoint. * * @param amount The amount to measure, which can be positive, negative or 0. * @param weights The weights available to us. * @param index The starting index into the weights Vector. * @return Whether the amount can be measured using the weights from the specified * index and forward. */bool isMeasurableRec(int amount, const Vector<int>& weights, int index) { if (index == weights.size()) { return amount == 0; } else { return isMeasurableRec(amount, weights, index + 1) || isMeasurableRec(amount + weights[index], weights, index + 1) || isMeasurableRec(amount - weights[index], weights, index + 1); }}bool isMeasurable(int amount, const Vector<int>& weights) { return isMeasurableRec(amount, weights, 0);}
CS106B Recursion and Iteration, Backtracking (2024)
Top Articles
Latest Posts
Recommended Articles
Article information

Author: Rev. Porsche Oberbrunner

Last Updated:

Views: 6396

Rating: 4.2 / 5 (73 voted)

Reviews: 80% of readers found this page helpful

Author information

Name: Rev. Porsche Oberbrunner

Birthday: 1994-06-25

Address: Suite 153 582 Lubowitz Walks, Port Alfredoborough, IN 72879-2838

Phone: +128413562823324

Job: IT Strategist

Hobby: Video gaming, Basketball, Web surfing, Book restoration, Jogging, Shooting, Fishing

Introduction: My name is Rev. Porsche Oberbrunner, I am a zany, graceful, talented, witty, determined, shiny, enchanting person who loves writing and wants to share my knowledge and understanding with you.