# Number of each coin demonination and combinations for a given amount

3973 views
7

I have seen some similar questions but couldn't get the hang of it. Basically, I have the following input:

``````   coins [1,2,3]
amount 4
``````

how many ways are there to give me the amount? So the above would be:

``````     1, 1, 1, 1
2,2
1,1,2
3,1
``````

So far, my approach is to loop the coins and slicing the icon collection on each loop, so reducing the size of coins that need to be used. But I couldn't put into action. Here is what I have attempted so far, which gives a correct output for only coins such as 1,1,1,1 or 2,2

My problem is looping 'the next' set of coins to see if their combination can give the needed amount reasonablly.

``````def cal2(amount, coins):
result = {}
def act(amount, coins):
if amount == 0 or len(coins) == 0:
return {}

else:
while (len(coins)>0):
firstCoin = coins

if amount % firstCoin == 0 and not firstCoin in result.keys():

parts = amount // firstCoin
if not firstCoin in result.keys():
result[firstCoin] = parts

if len(coins)>1:
# we still have coins to test....
nextCoin = coins

# remove current coin from the collection

coins = coins[1:]

act(amount,coins)
return result
``````

So:

``````      print(cal2(6, [1,2,3]))
# gives 1:6, 2:3, 3:2 which just means two 3 coins can give 6...
``````

9

You can use recursion:

``````coins = [1,2,3]
amount = 4
def combinations(d, _to, current):
if sum(current) == _to:
yield sorted(current)
else:
for i in d:
if sum(current+[i]) <= _to:
yield from combinations(d, _to, current+[i])

r = list(combinations(coins, amount, []))
final_result = [a for i, a in enumerate(r) if a not in r[:i]]
``````

Output:

``````[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2]]
``````

posted this