Number of each coin demonination and combinations for a given amount

3973 views python
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[0]

                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[1]

                # 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...

answered question

1 Answer

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

Have an answer?

JD

Please login first before posting an answer.