Link Search Menu Expand Document

Warmup: Exact Change

The problem

You are traveling through a country you’ve never visited before, which has a rather unusual monetary system. Coins come in strange denominations, and furthermore, the local shops only seem to take exact change. They won’t let you pay with a credit card or electronic payments either; you have to pay with the coins you have on you. Imagine you visit a shop and want to buy a souvenir. We will explore how to use backtracking and a recursive formulation of this problem to determine if we can pick some combination of coins that adds up to the souvenir price.

For example, suppose you have coins [3, 8, 7, 1, 2] and the price is 10. Can you make exactly 10?

  • 3 + 7 = 10. Yes!

What if the price is 12?

  • 3 + 8 + 1 = 12. Yes!

What if the price is 6?

  • 3 + 1 + 2 = 6. Yes!

What if the price is 15?

  • 8 + 7 = 15. Yes!

What if the price is 22?

  • 3 + 8 + 7 + 1 + 2 = 21. That is every coin you have, and it is still not enough. There is no way to make exactly 22. Failure.

There is no formula or shortcut to solve this. You have to try different combinations of coins and see if any of them work. This is a backtracking problem.

Connection to the double-or-add example

Recall the double-or-add problem from the backtracking introduction. In that problem, we started with a number and at each step we chose between two operations (double or add 3). Here, we go through the coins one at a time, and for each coin we choose between two options: take it (use it toward the total) or skip it (leave it in your pocket). The recursive structure is the same.

The key difference from the double-or-add problem is that we now have an array of coins and an index tracking which coin we are currently deciding about. This index advances by one on every recursive call — we always move on to the next coin regardless of whether we took the current one or skipped it.

Boolean version

First, write a function that determines whether it is possible to make exact change. Here is the pseudocode:

function canMakeChange(coins, index, remaining):
    // Base cases
    if remaining == 0:
        return true                   // Exact change made!
    if remaining < 0:
        return false                  // Overshot the price.
    if index >= length of coins:
        return false                  // Out of coins to try.

    // Try taking this coin
    if canMakeChange(coins, index + 1, remaining - coins[index]):
        return true

    // Taking it didn't work --- try skipping it
    if canMakeChange(coins, index + 1, remaining):
        return true

    // Neither worked
    return false

This follows the same pattern from the backtracking introduction: try one option, check if it worked, and if not, try the other.

Tracing an example

Let’s trace canMakeChange([3, 8, 7, 1, 2], 0, 10):

canMakeChange(index=0, remaining=10)   coin is 3
│  Try taking the 3 (remaining becomes 7)...
│
├── canMakeChange(index=1, remaining=7)   coin is 8
│   │  Try taking the 8 (remaining becomes -1)...
│   │
│   ├── canMakeChange(index=2, remaining=-1)
│   │      remaining < 0, return false.  ← overshot!
│   │
│   │  Taking it didn't work. Try skipping it...
│   │
│   ├── canMakeChange(index=2, remaining=7)   coin is 7
│   │   │  Try taking the 7 (remaining becomes 0)...
│   │   │
│   │   ├── canMakeChange(index=3, remaining=0)
│   │   │      remaining == 0, return true!
│   │   │
│   │   │  Taking the 7 worked! return true.
│   │
│   │  Skipping the 8 worked! return true.
│
│  Taking the 3 worked! return true.

Result: true

Notice the backtracking: the algorithm took the 3, then tried taking the 8, but 3 + 8 = 11 overshoots the target of 10. So it skipped the 8 and tried the 7 instead, and 3 + 7 = 10 works.

Some problems require much more backtracking. Try tracing canMakeChange([3, 8, 7, 1, 2], 0, 15) by hand. You should find that taking 3 first does not lead to a solution (no combination of the remaining coins adds up to 12), so the algorithm backtracks past the 3 and eventually discovers 8 + 7 = 15.

Path version

Now write a second function that returns which coins were used to make exact change. Following the pattern from the backtracking introduction, we return a string on success and "X" on failure.

When we take a coin, we include its value in the string. When we skip a coin, we do not add anything to the string. When we reach exact change, we return "!" to signal success.

So for coins [3, 8, 7, 1, 2] and target 10, the answer would be "3 7 !" — meaning we took the 3, took the 7, and reached the target.

You do not get pseudocode for this one. Instead, use the conversion pattern from the backtracking introduction: every place that returned true now returns a string ending in "!", every place that returned false now returns "X", and instead of checking a boolean you check whether the result equals "X". Two hints:

  • When you take a coin and the recursive call succeeds, prepend that coin’s value (and a space) to the result before returning it.
  • When you skip a coin and the recursive call succeeds, just pass the result through unchanged — only the coins you actually take should appear in the final string.

Tracing the path version

Let’s trace canMakeChangePath([3, 8, 7, 1, 2], 0, 10):

canMakeChangePath(index=0, remaining=10)   coin is 3
│  Try taking the 3 (remaining becomes 7)...
│
├── canMakeChangePath(index=1, remaining=7)   coin is 8
│   │  Try taking the 8 (remaining becomes -1)...
│   │
│   ├── canMakeChangePath(index=2, remaining=-1)
│   │      remaining < 0, return "X".  ← overshot!
│   │
│   │  Taking it didn't work. Try skipping it...
│   │
│   ├── canMakeChangePath(index=2, remaining=7)   coin is 7
│   │   │  Try taking the 7 (remaining becomes 0)...
│   │   │
│   │   ├── canMakeChangePath(index=3, remaining=0)
│   │   │      remaining == 0, return "!"
│   │   │
│   │   │  Taking the 7 worked! return "7 " + "!" = "7 !"
│   │
│   │  Skipping the 8 worked! return "7 !"
│
│  Taking the 3 worked! return "3 " + "7 !" = "3 7 !"

Result: "3 7 !"
Coins used: 3 and 7 (3 + 7 = 10) ✓

Again, compare this to the boolean version. The structure is the same. We just changed what we return.

What to implement

In the starter code, you will find a file called ExactChange.java with the following functions to fill in:

  • canMakeChange(int[] coins, int index, int remaining) — the boolean version. Returns true if it is possible to select coins starting from index that sum to remaining.

  • canMakeChangePath(int[] coins, int index, int remaining) — the path version. Returns a string listing the coins used (ending in "!"), or "X" if it is not possible.

There are also wrapper functions that call these with the right initial arguments, and a main method with test cases.

Test cases

Your program should produce the following output:

Coins: [3, 8, 7, 1, 2], Target: 10
  canMakeChange: true
  canMakeChangePath: 3 7 !

Coins: [3, 8, 7, 1, 2], Target: 12
  canMakeChange: true
  canMakeChangePath: 3 8 1 !

Coins: [3, 8, 7, 1, 2], Target: 6
  canMakeChange: true
  canMakeChangePath: 3 1 2 !

Coins: [3, 8, 7, 1, 2], Target: 15
  canMakeChange: true
  canMakeChangePath: 8 7 !

Coins: [3, 8, 7, 1, 2], Target: 22
  canMakeChange: false
  canMakeChangePath: X

Coins: [5, 11, 4, 9], Target: 20
  canMakeChange: true
  canMakeChangePath: 5 11 4 !

Coins: [5, 11, 4, 9], Target: 7
  canMakeChange: false
  canMakeChangePath: X

What to turn in

Turn in your completed ExactChange.java file. Make sure your output matches the test cases above.