Counting the number of money combinations

Hi, I’m doing a problem where I have to find the total number of combinations that a set of coins can make an amount. For example, if I have the coins 1 and 2, and I need to make 4, the total number of combinations of ones and twos that make 4 is three:

[1, 1, 1, 1], [2, 2], [1, 1, 2]

I need to write a program that can take a set of coin values and an amount of money and output the number of combinations that make that amount of money. I’m not asking for an answer per say, but a pointer or two is much appreciated. Thanks

This is a variant on a classic algorithms problem: making change.

Begin with “brute force.” How would you do it, given the coins and the amount, but lacking a computer? See if you can come up with a step-by step solution, assuming that the coins are in front of you on the table, then try to write that down stepwise in a form that an eight year-old can follow.

Only then should you begin to code it.

(The brute force method probably won’t work if you are doing this as a coding challenge - it’s too slow. But just ask Dr. Google about the “making change” problem for further hints.)

1 Like