Algorithm to determine coin combinations

c++ algorithm combinations combinatorics
ahota picture ahota · May 5, 2011 · Viewed 14.4k times · Source

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)

Answer

taskinoor picture taskinoor · May 5, 2011

This problem is well known as coin change problem. Please check this and this for details. Also if you Google "coin change" or "dynamic programming coin change" then you will get many other useful resources.

Related questions

Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
Generating combinations in c++

I have been searching a source code for generating combination using c++. I found some advanced codes for this but that is good for only specific number predefined data. Can anyone give me some hints, or perhaps, some idea to …

Read More
What's time complexity of this algorithm for finding all combinations?

Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: [ [2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4], ] Personally I think, time complexity = O(n^k), n and k are input. Thank …

Read More