CS 2 (Winter 2026) Review Lab: Recursive Backtracking Problems

Review Lab: Recursive Backtracking Problems

Setup

Register for the lab using http://register.caltech.codes/ and clone the repository as explained in the setup instructions.

Goals and Outcomes

In this lab, you will solve various smaller problems using recursive backtracking! By the end of this lab, you will…

Fun With Strings

public static Set<String> generateStrings(String charSet, char c, int k, int len)

Given a set of characters charSet, a special character c, an integer k, and an integer len, produce a set containing all Strings of length equal to len, with k instances of c, only using characters from charSet.

An example (with pseudocode): the call generateStrings({'a', 'b'}, 'a', 1, 3) would return the set {"abb", "bab", "bba"}, as it is the set of all Strings of length 3 with only 1 instance of a, using only a’s and b’s.

Magic Squares

A number square of size n is an int[][], with dimensions n x n, made up of unique positive integers from 1 to n^2. A magic number square is a number square with the additional property that the sum of numbers in each row, column, and both diagonals are all the same. The goal for this entire problem is to write a function that fills in a number square such that it is a magic number square upon returning (if it is possible to find one). Throughout this question, we will use another Pair class, like before. This time, Pairs have two methods p.x() and p.y().

You should use the following methods in your implementation

public static boolean doesNotCreateConflict(Pair p, int[][] square)

Returns true when the addition of the value at cell p does not create a conflict that makes the magic number square impossible to complete correctly.

public static boolean isFull(int[][])

Returns true iff there are no zeroes left in the square.

public static Pair getNextZeroEntry(int[][] square)

Returns a Pair indicating the coordinates of some entry in the number square that is currently zero.

public static boolean fillMagicSquare(int[][] square)

Returns true if the square can be filled in properly as a magic square, and false otherwise.

Note: the square should be filled in (if possible) at the conclusion of this method.

Subset Sum

You might have come across the following problem in real life: imagine you want to buy something that costs $40 in cash, and you have some bills in your wallet. Let’s say you have 2 $10 bills, 1 $20 bill, and 5 $5 bills. In what ways could you make $40 from the cash you have?

Another way to phrase this problem is, given the set {10, 10, 20, 5, 5, 5, 5, 5} (the bills you have in your wallet), what are the subsets of this set whose elements add up to 40 (your “target sum”)? This problem with bills in your wallet is a specific example of the subset sum problem. The subset sum problem is as follows: given a set of nonnegative integers and a nonnegative target sum, find every subset that adds up to the target sum.

The set of nonnegative integers allows repeated values: this is different from a Set, in which there are no repeats. Thus, our set is a multiset, a set allowing multiple instances of the same value. We have provided you with the MultiSet class, which you can see in the file MultiSet.java. The “sets” and “subsets” of our subset sum problem will thus be represented as MultiSets. The MultiSet class has an additional method called getHighestValue, which will return the greatest element in the MultiSet. For instance, if your MultiSet is {2, 2, 8, 3, 8, 4, 7}, getHighestValue will return 8.

Below is the method header and description of the subsetSum method you will implement.

public static Set<MultiSet<Integer>> subsetSum(MultiSet<Integer> inputSet, int sum)

Returns a Set of subsets of inputSet where the sum of all elements in the subset equal sum.

This method returns a Set of all subsets that “work.” For instance, in our “buying something for $40 in cash” example, we would have:

There are no Gitlab tests for this lab, as it is completely optional!