These problems will give you more practice with concepts covered on the mid-quarter exam.
Programming in C++
1. countNumbers (count.cpp)
Topics: Vectors, strings, file reading, while true, conditional statements, Stanford C+++ library
The function countNumbers
reads a text file and prints the number of times a user entered number appears in that text file. A user can continually enter numbers until they hit "Enter" or "Return" on their keyboard. Here are some library functions that will be useful for this task:
readLines
, to read all lines from a file stream into a VectorstringSplit
, to divide a string into tokensgetLine
, to read a line of text entered by the userstringIsInteger
, to confirm a string of digits is valid integer
In particular you will be asked to write the following function
void countNumbers(string filename)
When given the following file, named numbers.txt
, as input, your function should print 1 when a user enters 42. Similarly, when the user enters another number like 9, your function should print 2. Finally, the function ends when the user presses "Return".
42 is the Answer to the Ultimate Question of Life, the Universe, and Everything
This is a negative number: -9
Welcome to CS106B!
I want to own 9 cats and 9 dogs.
/*
* Function: countNumbers
* ----------------------
* Write a program to read through a given file and count the
* the number of times a user inputed number appears in that file. You
* can assume that numbers will be composed entirely of numerical digits,
* optionally preceded by a single negative sign.
*/
void countNumbers(string filepath) {
ifstream in;
if (!openFile(in, filepath)) {
return;
}
Vector<string> lines = readLines(in);
while (true) {
string number = getLine("Enter a number to check (enter to quit): ");
if (number == "") {
break;
}
if (!stringIsInteger(number)) {
cout << "Please enter a number" <<endl;
continue;
}
int count = 0;
for (string line : lines) {
Vector<string> tokens = stringSplit(line, " ");
for (string t : tokens) {
if (t == number) {
count ++;
}
}
}
cout << "Number " << number << " appeared " << count << " times in the file." << endl;
}
}
2. Debugging Deduplicating (deduplicate.cpp
)
Topics: Vector, strings, debugging
Consider the following incorrect C++ function, which accepts as input a Vector<string>
and tries to modify it by removing adjacent duplicate elements:
⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️
void deduplicate(Vector<string> vec) {
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == vec[i + 1]) {
vec.remove(i);
}
}
}
⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️⚠️
The intent behind this function is that we could do something like this:
Vector<string> hiddenFigures = {
"Katherine Johnson",
"Katherine Johnson",
"Katherine Johnson",
"Mary Jackson",
"Dorothy Vaughan",
"Dorothy Vaughan"
};
deduplicate(hiddenFigures);
// hiddenFigures = ["Katherine Johnson", "Mary Jackson", "Dorothy Vaughan”]
The problem is that the above implementation of deduplicate
does not work correctly. In particular, it contains three bugs. First, find these bugs by writing test cases that pinpoint potentially erroneous situations in which the provided code might fail, then explain what the problems are, and finally fix those errors in code.
There are three errors here:
- Calling
.remove()
on theVector
while iterating over it doesn’t work particularly nicely. Specifically, if you remove the element at indexi
and then incrementi
in the for loop, you’ll skip over the element that shifted into the position you were previously in. - There’s an off-by-one error here: when
i = vec.size() - 1
, the indexingvec[i + 1]
reads off the end of theVector
. - The
Vector
is passed in by value, not by reference, so none of the changes made to it will persist to the caller.
Here are corrected versions of the code:
// solution 1
void deduplicate(Vector<string>& vec) {
for (int i = 0; i < vec.size() - 1; ) {
if (vec[i] == vec[i + 1]) {
vec.remove(i);
} else {
i++;
}
}
}
// solution 2
void deduplicate(Vector<string>& vec) {
for (int i = vec.size() - 1; i > 0; i--) {
if (vec[i] == vec[i - 1]) {
vec.remove(i);
}
}
}
ADTs
1. Mirror
Topic: Grids
Write a function mirror
that accepts a reference to a Grid
of integers as a parameter and flips the grid along its diagonal. You may assume the grid is square; in other words, that it has the same number of rows as columns. For example, the grid below that comes first would be altered to give it the new grid state shown afterwards:
Original state:
{ { 6, 1, 9, 4},
{-2, 5, 8, 12},
{14, 39, -6, 18},
{21, 55, 73, -3} }
Mirrored state:
{ {6, -2, 14, 21},
{1, 5, 39, 55},
{9, 8, -6, 73},
{4, 12, 18, -3} }
Bonus: How would you solve this problem if the grid were not square?
// solution
void mirror(Grid<int>& grid) {
for (int r = 0;r < grid.numRows(); r++) {
// start at r+1 rather than 0 to avoid double-swapping
for (int c = r + 1; c < grid.numCols(); c++) {
int temp = grid[r][c];
grid[r][c] = grid[c][r];
grid[c][r] = temp;
}
}
}
// bonus
void mirror(Grid<int>& grid) {
Grid<int> result(grid.numCols(), grid.numRows());
for (int r = 0; r < grid.numRows(); r++) {
for (int c = 0; c < grid.numCols(); c++) {
result[r][c] = grid[c][r];
}
}
grid = result;
}
2. Collection Mystery
Topics: Stacks, queues
void collectionMystery(Stack<int>& s)
{
Queue<int> q;
Stack<int> s2;
while (!s.isEmpty()) {
if (s.peek() % 2 == 0) {
q.enqueue(s.pop());
} else {
s2.push(s.pop());
}
}
while (!q.isEmpty()) {
s.push(q.dequeue());
}
while(!s2.isEmpty()) {
s.push(s2.pop());
}
cout<< s << endl;
}
Write the output produced by the above function when passed each of the following stacks. Note that stacks and queues are written in front to back order, with the oldest element on the left side of the queue/stack.
Stacks:
{1, 2, 3, 4, 5, 6} ________________________________________
{42, 3, 12, 15, 9, 71, 88} ________________________________________
{65, 30, 10, 20, 45, 55, 6, 1} ________________________________________
{6, 4, 2, 1, 3, 5}
{88, 12, 42, 3, 15, 9, 71}
{6, 20, 10, 30, 65, 45, 55, 1}
3. Reversing a Map
Topic: Nested data structures
Write a function
Map<int, Set<string>> reverseMap(Map<string, int>& map)
that, given a Map<string, int>
that associates string values with integers, produces a Map<int, Set<string>>
that’s essentially the reverse mapping, associating each integer value with the set of strings that map to it. (This is an old job interview question from 2010.)
Here’s one possible implementation.
Map<int, Set<string>> reverseMap(Map<string, int>& map) {
Map<int, Set<string>> result;
for (string oldKey : map) {
// Note: we check containsKey here but this isn't
// necessary since Maps auto-initialize values
// on square bracket access if the key is not
// present
if (!result.containsKey(map[oldKey])) {
result[map[oldKey]] = {};
}
result[map[oldKey]].add(oldKey);
}
return result;
}
4. Stack vs Vector showdown
Topics: Stacks, vectors
We will analyze a simple program that emulates a text editor. The program accepts input from a user which can be of two forms:
-
ADD string: This adds a one word string into the text editor
-
UNDO: This removes the most recently added string from the editor.
When the user finishes providing input (by hitting ENTER), we print a string which represents the words in the text editor, in the order they were added.
Example: If we receive user input like "ADD I", "ADD Love", "ADD 106A", "UNDO", "ADD 106B", the program prints out "I love 106B".
int main() {
Stack<string> words;
while (true) {
string command = getLine("Enter a command (press enter to quit): ");
if (command == "") {
break;
}
Vector<string> splitCommands = stringSplit(command, " ");
if (splitCommands[0] == "ADD") {
words.push(splitCommands[1]);
} else if (splitCommands[0] == "UNDO") {
words.pop();
}
}
string result;
while (!words.isEmpty()) {
result = words.pop() + result;
}
cout << result << endl;
return 0;
}
5. Maps
Topic: Maps
Here, we analyze a simple program that uses maps to count elements in a vector
Map<string, int> countElements(Vector<string>& names) {
Map<string, int> frequency;
for (string name: names) {
// When using the square bracket syntax([]), we don't need to initialize
// names in the map before adding unto it. If name doesn't already exist
// in the map, [] in the Stanford Map will initialize it for us.
frequency[name] += 1;
}
return frequency;
}
Big-O
1. Oh No, Big-O, Too Slow
Topics: Big-O, code analysis, ADTs
What is the Big O runtime of the following functions, in terms of the variable N.
Code Snippet A
Vector<int> v;
for (int i = 1; i <= N + 2; i++) {
v.add(i);
}
for (int i = 1; i < N; I ++) {
v.insert(0, i);
}
Code Snippet B
Set<string> s;
for (int i = 1; i <= N - 5; i++) {
s.add(i);
}
Code Snippet C
Map<int, int> m;
for (int i = 1; i <= 3*N; i++) {
m[i] = i * 4;
}
Code Snippet D
Stack<int> s;
for (int i = 1; i <= N; i++) {
s.push(i)
}
for (int i = 1; i <= N/2; i++) {
s.pop(i)
}
Code Snippet A has a runtime complexity of O(N^2): The first for loop runs in
O(N), because adding to a vector is constant time O(1), and we add N time. The
second for loop runs N times, but inside this loop we perform an O(N)
operation, which is inserting at the front of a vector. Therefore Big O of
second loop is O(N^2). This makes O(N) + O(N^2) = O(N^2), because we only pick
the highest order Big O.
Code Snippet B has a runtime complexity of O(NlogN): The first for loop runs in
N. Inside of the loop, we perform an O(logN) operation, which is adding to a set.
This makes O(N * logN) = O(NlogN)
Code Snippet C has a runtime complexity of O(NlogN): This is very similar to B
above. Inserting in a map also runs in O(logN). If we do that N times, we get
O(NlogN).
Code Snippet D has a runtime complexity of O(N): Pushing unto a stack runs in
O(1) time, so the first for loop runs in O(N). Popping off a stack runs in O(1)
time so the second for loop runs in O(N/2) = O(N). In total, O(N) + O(N) = O(N),
since we throw away multipliers.
2. More Big-O
Topics: Big-O, code analysis, ADTs
Below are five functions. Determine the big-O runtime of each of those pieces of code, in terms of the variable n
.
void function1(int n) {
for (int i = 0; i < n; i++) {
cout << '*' << endl;
}
}
void function2(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << '*' << endl;
}
}
}
void function3(int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << '*' << endl;
}
}
}
void function4(int n) {
for (int i = 1; i <= n; i *= 2) {
cout << '*' << endl;
}
}
Finally, what is the big-O runtime of this function in terms of n
, the number of elements in v
?
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
Vector<int> values = v.subList(0, i);
for (int j = 0; j < values.size(); j++) {
result += values[j];
}
}
return result;
}
- The runtime of this code is
O(n)
: We print out a single star, which takes timeO(1)
, a total ofn
times. - The runtime of this code is
O(n^2)
. The inner loop doesO(n)
work, and it runsO(n)
times for a net total ofO(n^2)
work. - This one also does
O(n^2)
work. To see this, note that the first iteration of the inner loop runs forn – 1
iterations, the next forn – 2
iterations, thenn – 3
iterations, etc. Adding all this work up across all iterations gives(n – 1) + (n – 2) + … + 3 + 2 + 1 + 0 = O(n^2)
. - This one runs in time
O(log n)
. To see why this is, note that afterk
iterations of the inner loop, the value ofi
is equal to2^k
. The loop stops running when2^k
exceedsn
. If we set2^k = n
, we see that the loop must stop running afterk = log₂ n
steps.
Another intuition for this one: the value of i doubles on each iteration, and you can only doubleO(log n)
times before you overtake the valuen
.
For the final function, Let’s follow the useful maxim of "when in doubt, work inside out!"" The innermost for loop (the one counting with j
) does work proportional to the size of the values list, and the values list has size equal
to i
on each iteration. Therefore, we can simplify this code down to something that looks like this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
Vector<int> values = v.subList(0, i);
do O(i) work;
}
return result;
}
Now, how much work does it take to create the values vector? We’re copying a total of i
elements from v
, and so the work done will be proportional to i
. That gives us this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
do O(i) work;
do O(i) work;
}
return result;
}
Remember that doing O(i)
work twice takes time O(i)
, since big-O ignores constant factors. We’re now left with this:
int squigglebah(Vector<int>& v) {
int result = 0;
for (int i = 0; i < v.size(); i++) {
do O(i) work;
}
return result;
}
This is the same pattern as function2 in the previous problem, and it works out to O(n^2)
total time.
Recursion
1. Recursion Mystery Part 1
Topics: Recursive function calls, return value tracing
Code Snippet A
int recursionMystery(int x, int y) {
if (x < y) {
return x;
} else {
return recursionMystery(x - y, y);
}
}
For each call to the above recursive function, indicate what value is returned by the function call.
Call Return value
recursionMystery(6, 13); ______________
recursionMystery(14, 10); ______________
recursionMystery(37, 12); ______________
6
4
1
2. Recursion Mystery Part 2
Topics: Recursive function calls, output tracing
void recursionMystery2(int x, int y) {
if (y == 1) {
cout << x;
} else {
cout << (x * y) << ", ";
recursionMystery2(x, y - 1);
cout << ", " << (x * y);
}
}
For each call to the above recursive function, write the output that would be produced, as it would appear on the console.
Call Output
recursionMystery2(4, 1); ___________________________________
recursionMystery2(4, 2); ___________________________________
recursionMystery2(8, 2); ___________________________________
recursionMystery2(4, 3); ___________________________________
recursionMystery2(3, 4); ___________________________________
4
8, 4, 8
16, 8, 16
12, 8, 4, 8, 12
12, 9, 6, 3, 6, 9, 12
3. Sum of Squares
Topics: Recursion
Write a recursive function named sumOfSquares
that takes an int n
and returns the sum of squares from 1
to n
. For example, sumOfSquares(3)
should return 1^2 + 2^2 + 3^2 = 14. If n
is negative, you should report an error to that effect.
int sumOfSquares(int n) {
if (n < 0) {
error("Value of provided n was negative");
} else if (n == 0) {
return 0;
} else {
return n * n + sumOfSquares(n-1);
}
}
4. Zig Zag
Topics: Recursion, printing output to console
Write a recursive function named zigzag
that returns a string of n
characters as follows. The middle character (or middle two characters if n
is even) is an asterisk (*). All characters before the asterisks are '<'
. All characters after are '>'
. Report an error if n
is not positive.
Call Output
zigzag(1) *
zigzag(4) <**>
zigzag(9) <<<<*>>>>
string zigzag(int n) {
if (n < 1) {
error("The value of n was negative");
} else if (n == 1) {
return "*";
} else if (n == 2) {
return "**";
} else {
return "<" + zigzag(n-2) + ">";
}
}
5. Double Stack
Topics: Recursion, stacks
Write a recursive function named doubleStack
that takes a reference to a stack of ints and replaces each integer with two copies of that integer. For example, if s
stores {1, 2, 3}
, then doubleStack(s)
changes it to {1, 1, 2, 2, 3, 3}
.
void doubleStack(Stack<int>& s)
{
if (!s.isEmpty()) {
int n = s.pop();
doubleStack(s);
s.push(n);
s.push(n);
}
}
6. String Subsequences
Topics: Recursion, verifying properties
Write a recursive function named isSubsequence
that takes two strings and returns true
if the second string is a subsequence of the first string. A string is a subsequence of another if it contains the same letters in the same order, but not necessarily consecutively. You can assume both strings are already lower-cased.
Call Output
isSubsequence("computer", "core") false
isSubsequence("computer", "cope") true
isSubsequence("computer", "computer") true
bool isSubsequence(string big, string small)
{
if (small.empty()) {
return true;
} else if (big.empty()) {
return false;
} else {
if (big[0] == small[0]) {
return isSubsequence(big.substr(1), small.substr(1));
} else {
return isSubsequence(big.substr(1), small);
}
}
}
7. Recursion and Time Complexity and Exponents, (Big-)O My
Topics: Recursion, time complexity, Big-O, algorithm comparison
Below is a simple function that computes the value of m^n when n is a nonnegative integer:
int raiseToPower(int m, int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= m;
}
return result;
}
1) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1)
to multiply two numbers.
2) If it takes 1 microsecond (μs) to compute raiseToPower(100, 100)
, approximately how long will it take to compute raiseToPower(200, 10000)
?
Below is a recursive function that computes the value of m^n
when n
is a nonnegative integer:
int raiseToPower(int m, int n) {
if (n == 0) return 1;
return m * raiseToPower(m, n - 1);
}
3) What is the big-O complexity of the above function, written in terms of m
and n
? You can assume that it takes time O(1)
to multiply two numbers.
4) If it takes 1μs to compute raiseToPower(100, 100)
, approximately how long will it take to compute raiseToPower(200, 10000)
?
Here’s an alternative recursive function for computing m^n
that uses a technique called exponentiation by squaring. The idea is to modify the recursive step as follows:
- If
n
is an even number, then we can writen
asn = 2k
. Thenm^n = m^(2k) = (m^k)^2
. - If
n
is an odd number, then we can writen
asn = 2k + 1
. Thenm^n = m^(2k+1) = m * m^(2k) = m * (m^k)^2
.
Based on this observation, we can write this recursive function:
int raiseToPower(int m, int n) {
if (n == 0) {
return 1;
} else if (n % 2 == 0) {
int halfPower = raiseToPower(m, n / 2);
return halfPower * halfPower;
} else {
int halfPower = raiseToPower(m, n / 2);
return m * halfPower * halfPower;
}
}
5) What is the big-O complexity of the above function, written in terms of m
and n
? You can assume that it takes time O(1)
to multiply two numbers.
6) If it takes 1μs to compute raiseToPower(100, 100)
, approximately how long will it take to compute raiseToPower(200, 10000)
?
-
This function runs in time
O(n)
. It runs the loopn
times, at each step doingO(1)
work. There is no dependence onm
in the runtime. -
We know that this code runs in time
O(n)
, so it scales roughly linearly with the size ofn
. Therefore, if it took 1μs to compute a value whenn = 100
, it will take roughly 100 times longer when we plug inn = 10000
. As a result, we’d expect this code would take about 100μs to complete. -
If we trace through the recursion, we’ll see that we make a total of
n
recursive calls, each of which is only doingO(1)
work. Adding up all the work done by these recursive calls gives us a total ofO(n)
work, as before. -
As before, this should take about 100μs.
-
Notice that each recursive call does
O(1)
work (there are no loops anywhere here), then calls itself on a problem that’s half as big as the original one. This means that onlyO(log n)
recursive calls will happen (remember that repeatedly dividing by two is the hallmark of a logarithm), so the total work done here isO(log n)
. -
We know that the runtime when n = 100 is roughly 1μs. Notice that 100^2 = 10,000, so we’re essentially asking for the runtime of this function when we square the size of the input. Also notice that via properties of logarithms that
log n^2 = 2 log n
. Therefore, since we know the runtime grows roughly logarithmically and we’ve squared the value ofn
, this should take about twice as long as before, roughly 2μs.
Backtracking
1. Longest Common Subsequence
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;
}
}
}
2. Cracking Passwords
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 and raise an error 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) {
error("max length cannot be negative!);";
}
return crackHelper("", maxLength);
}
3. Change We Can Believe In
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
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 both solutions 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:
SOLUTION 1
/**
* 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;
/* What is this for loop doing? We use this loop to explore
* all the options of coins we have. To make the change, all of
* the coins in our set are valid options, so we make recursive
* calls, each of which chooses a coin. It is very similar to
* the subset problems we've done in class, where we have two
* choices(either add or don't add to the set). Here, we either
* add coin1 or coin2, ..., coinN.
*/
for (int coin: coins) {
// If this coin doesn’t exceed the total, try using it.
if (coin <= cents) {
/* Use this coin in the change. We add 1 because
we've used one coin
*/
int numCoinsUsed = 1 +
fewestCoinsFor(cents - coin, coins);
/* We want to find the fewest number of coins,
* so compare number of coins used when we use
* the current coin to the minimum number of
* coins so far.
*/
bestSoFar = min(bestSoFar, numCoinsUsed);
}
}
return bestSoFar;
}
}