CODEWITHSUNDEEP
pythonalgorithm
Nie Selam
Nie Selam

Reputation: 1451

Number of each coin demonination and combinations for a given amount

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

Upvotes: 0

Views: 65

Answers (1)

Ajax1234
Ajax1234

Reputation: 71451

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

Upvotes: 1

Related Questions