## Coin Change, Part 1

### May 17, 2013

It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.

The solution is usually stated in recursive form: if *c* is the first coin in the set of coins *cs* and *n* is the target, the solution is the number of ways to reach the target after removing *c* from *cs* plus the number of ways to reach *n* − *c* using all the coins in *cs*. The algorithm to make a list of the coins, instead of the count, is the same, but keeping track of the list of coins instead of the count.

Your task is to write two functions, one to determine the count and one to determine the list of coins. 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.

[…] today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be […]

My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/17/programming-praxis-coin-change-part-1/ for a version with comments):

Here is a Ruby program with both functions

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

coin-change1 output

hosted with ❤ by GitHub

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

coin-change1.rb

hosted with ❤ by GitHub

Here is the output:

[…] This post presents C# solutions to a coin change problem as described inÂ https://programmingpraxis.com/2013/05/17/coin-change-part-1. […]

I have done this exercise using a simple method: I divide the total (T) by the first coin (C1). I take the integer part of this division (n1=T//c1). n1 represents the maximum number of possiblities of having c1 in any combinaison. After that, I do the same process for finding the total minus 0, 1,…, n1*c1 now using just the new set (C2, C3, C4).

Here is the program in Python, and it works well: the result is outputed very fast.

c1=25

c2=10

c3=29

c4=3

T=40

C=[]

for i in range(0, (T//c1)+1):

if T-(i

c1)==0:c1)//c2)+1):C.append([i,0,0,0])

continue

for j in range(0, ((T-i

if T-i

c1-jc2==0:C.append([i,j,0,0])

continue

for w in range(0, ((T-i

c1-jc2)//c3)+1):if (T-i

c1-jc2-wc3)%c4 == 0:c1-jC.append([i,j,w,(T-i

c2-wc3)//c4])for i in C:

print(i)

print(len(C))

[…] solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be […]