Coin Change, Part 3
May 24, 2013
Our exercise today is similar to the two previous exercises on the coin change problem, but doesn’t directly involve coins. But we’ll still call it a coin change problem because I can’t think of a better name.
As in the coin change problems, we are given a target to which a set of coins is intended to sum. But instead of a list of coins, we are given a number n and assume that we have one of each denomination of coin from 1 through n. Unlike the coin change problems, we have only one of each coin, not an infinite number of them.
The problem is to figure out all the ways to combine coins to reach the desired sum. For instance, if the sum s is 10 and n is 10, the ways to combine the coins are (10), (9 1), (8 2), (7 3), (7 2 1), (6 4), (6 3 1), (5 4 1), (5 3 2), and (4 3 2 1). Note that a set like (6 2 2) is not possible because only one 2-coin is available. As in the two previous exercises, we are interested in both a function to make a list of all the solutions and a separate function that simply counts them.
Your task is to write the two programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 