Algorithm to determine coin combinations

Posted by A.J. on Stack Overflow See other posts from Stack Overflow or by A.J.
Published on 2011-05-05T11:50:34Z Indexed on 2012/06/19 3:16 UTC
Read the original article Hit count: 351

I was recently faced with a prompt for a programming algorithm that I had no idea what to do for. I've never really written an algorithm before, so I'm kind of a newb at this.

The problem said to write a program to determine all of the possible coin combinations for a cashier to give back as change based on coin values and number of coins. For example, there could be a currency with 4 coins: a 2 cent, 6 cent, 10 cent and 15 cent coins. How many combinations of this that equal 50 cents are there?

The language I'm using is C++, although that doesn't really matter too much.

edit: This is a more specific programming question, but how would I analyze a string in C++ to get the coin values? They were given in a text document like

4 2 6 10 15 50 

(where the numbers in this case correspond to the example I gave)

© Stack Overflow or respective owner

Related posts about c++

Related posts about algorithm