Recursive Backtracking

This week’s section exercises continue our exploration of recursion to tackle even more challenging and interesting problems. In particular, this week's section problems center around recursive backtracking, a very powerful and versatile problem solving technique.

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter project

1. Win some, lose sum (sum.cpp)

Topics: recursive backtracking

Write a recursive function named canMakeSum that takes a reference to a Vector<int> and an int target value and returns true if it is possible to have some selection of values from the Vector that sum to the target value. In particular, you should be implementing a function with the following declaration

bool canMakeSum(Vector<int>& values, int target)

For example, let's say that we executed the following code

Vector<int> nums = {1,1,2,3,5};
canMakeSum(nums, 9)

We should expect that the call to canMakeSum should return true. Given the values specified in nums, we can select 1, 3, and 5 such that 5 + 3 + 1 = 9.

However, let's say that we executed the following code instead

Vector<int> nums = {1,4,5,6};
canMakeSum(nums, 8);

We should expect that the call to canMakeSum in this case should return false, since there is no possible combination of values from the vector that sum up to the target value of 8.

SOLUTION 1
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar) {
	if (v.isEmpty()) {
		return sumSoFar == target;
	}
	/* Here we choose the last element in the vector.
	 * We could have chosen any element, but the last
	 * is the easiest and fastest method.
	 */
	int choice = v[v.size() - 1];
	v.remove(v.size() - 1);

	bool with = canMakeSumHelper(v, target, sumSoFar + choice);
	bool without = canMakeSumHelper(v, target, sumSoFar);

	// And then we unchoose, by adding this back!
	v.add(choice);

	return with || without;
}

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

SOLUTION 2
/*
 * This solution is similar to the one above, except it uses 
 * an additional index parameter in a vector to make the choices, 
 * instead of removing from the vector like solution 1 did.
 */
bool canMakeSumHelper(Vector<int>& v, int target, int sumSoFar, int index) {
	if (index >= v.size()) {
		return sumSoFar == target;
	}

	// This is our choice now. Remember we can choose any element
	// in the vector, so we choose the element at 'index'
	int choice = v[index];

	bool with = canMakeSumHelper(v, target, sumSoFar + choice, index + 1);
	bool without = canMakeSumHelper(v, target, sumSoFar, index + 1);
	
	// We don't have to add back, because we never removed!
	return with || without;
}

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

2. Shrink Words (shrink.cpp)

Topics: recursive backtracking

Write a recursive function named shrinkWord that takes a string word and a Lexicon of words, and shrinks the word to the smallest possible word that can be found in the Lexicon. You can think of a the lexicon as a set of all words in the English dictionary. Checkout the documentation for Lexicon to learn more.

string shrinkWord(string input, Lexicon& lex) 

The function is best described by this example below:

Given a string "starter", we can shrink it to "a" through these: starter -> starer (by removing the second t) -> stare (by removing the second r) -> tare (by removing s) -> are (by removing t) -> ae (by removing r) -> a (by removing e). Hence, we'll return "a". Note that all the intermediate words are english words.

As another example, given string "baker", we can shrink it to "bake" through these: baker -> bake (remove r). We can't shrink any further because if we remove a any another letter, we can't find the resulting word in the lexicon. Hence, we'll return "bake".

Finally, for "fishpond", we can't make a single transformation. So we'll return "fishpond", unchanged.

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

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?

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

that, given a number n, returns the number of ways you can tile a 2 × n grid with 2 × 1 dominoes.

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