CODEWITHSUNDEEP
pythondynamic-programming
Lucas Park
Lucas Park

Reputation: 3

Having problem with adding iteration into recursion

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.

Upvotes: 0

Views: 43

Answers (1)

Jerven Clark
Jerven Clark

Reputation: 1219

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

Upvotes: 1

Related Questions