Having problem with adding iteration into recursion

Question

I was trying to solve a dp problem (checking if given amount can be broken down with given coins with different values, assuming there are infinite number of coins available for each valued coins)

def istrue(coins, amount):

    if (amount - coins[0] > 0):
        holder = False

        while (holder == False and len(coins) != 0):
            holder = holder or istrue(coins, amount - coins[0])

            if(len(coins) != 0):
                coins.pop(0)

        return holder

    elif (amount - coins[0] < 0):
        return False

    else:
        return True

And was not sure what would be an appropriate way of iterating through the given coins. Currently, I am having trouble inside the while loop. (If the amount left to break down is bigger than current value of a coin, it moves onto the next coin) But the amount to be break down also goes back a step because I used pop.. Any hints for fixing this? example) coins: [7,3]. amount: 20. -> as it reaches 6 (20-7-7), the index for coins array moves on but also the amount gets backed up a step because I pop()ed it.

Don't store the denominations themselves. Sort coins in order, try to break down starting from the largest coins, and for each DP step store an index of coin from where you reached the current step — Alexey S. Larionov
– Alexey S. Larionov, Commented Dec 29, 2021 at 14:41
Is "denominations" the variable "coins"? When you say you have an infinite amount of coins, do you mean an infinite number of denominations? Or an infinite amount of money? I'm confused about what you're trying to accomplish here. — Sarah Messer
– Sarah Messer, Commented Dec 29, 2021 at 14:43
E.g. you have 20 total, after first break down you have 13 (remember index of coin 7), then you have 6 (remember index of coin 7), then 3 (remember index of coin 3), then 0 (remember index of coin 3). If you need to recover a denomination, iterate your steps - you remembered 3, then 3, then 7, then 7 — Alexey S. Larionov
– Alexey S. Larionov, Commented Dec 29, 2021 at 14:44
Sorry for the confusion. I meant limited number of coin types and infinite amount of coins for each type. — Lucas Park
– Lucas Park, Commented Dec 29, 2021 at 15:30
Thank you all for the answers and comments! I managed to figure it out after all the help :) — Lucas Park
– Lucas Park, Commented Dec 29, 2021 at 15:32

Jerven Clark · Accepted Answer · 2021-12-29 15:07:45Z

1

You can loop over your coins instead of doing a recursion:

def istrue(coins, amount):
    coins.sort(reverse=True)
    _, remainder = divmod(amount, coins[0])
    coins.pop(0)
    for coin in coins:
        _, remainder = divmod(remainder, coin)

    return not remainder

edited Dec 29, 2021 at 15:07

answered Dec 29, 2021 at 14:46

Jerven Clark

1,2292 gold badges14 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Stef Over a year ago

Is there some stylistic reason to use divmod rather than % here? (I'm genuinely asking, not criticizing).

Jerven Clark Over a year ago

Nothing really, just leaving room for when the value for each denomination is needed.

ATony Over a year ago

Doesn't this approach assume that the coin values are sorted in decreasing order?

Jerven Clark Over a year ago

Updated the answer to cover for unsorted coins.

Collectives™ on Stack Overflow

Having problem with adding iteration into recursion

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related