CODEWITHSUNDEEP
pythonalgorithmrecursion
sam202252012
sam202252012

Reputation: 165

Recursion Coin Change problem gives wrong answer

Why does my code, print out "Found Solution" 7 times inside of 4 times when the coins are [1,2,3] the change in cents is 4. There should only be 4 possible solutions. What did I do wrong here?

def coinChange(nCents, coins, total):
    if (total == nCents):
        print("Found solution")
        return 
    if (total > nCents):
        return
    if (total < nCents):
        for i in range(len(coins)):
            coinChange(nCents, coins, total+coins[i])

coins = [1,2,3]

coinChange(4, coins, 0)

Upvotes: 0

Views: 72

Answers (2)

Daniel Hao
Daniel Hao

Reputation: 4981

This is NOT the direct answer to the PO. But it's rather to show another way - Dynamic Programming way to solve the same problem:

def coin_ways(coins, amount):
    dp = [[] for _ in range(amount+1)]
    
    dp[0].append([])      # or table[0] = [[]], if prefer

    for coin in coins:
        for x in range(coin, amount+1):
            dp[x].extend(ans + [coin] for ans in dp[x-coin])
    #print(dp)
    
    return dp[amount]


if __name__ == '__main__':
    coins = [1, 2, 3]  # 
 
    print(coin_ways(coins, 4))

Upvotes: 1

Mark
Mark

Reputation: 92471

A direct answer to why can be found by keeping track of the coins you have used and printing them with the results. That will make clear why you are getting seven results:

def coinChange(nCents, coins, total, coin_list = None):
    if coin_list is None:
        coin_list = []
    if (total == nCents):
        print("Found solution", coin_list)
        return 
    if (total > nCents):
        return
    if (total < nCents):
        for i in range(len(coins)):
            coinChange(nCents, coins, total+coins[i], coin_list + [coins[i]])

coins = [1,2,3]

coinChange(4, coins, 0)

This prints:

Found solution [1, 1, 1, 1]
Found solution [1, 1, 2]
Found solution [1, 2, 1]
Found solution [1, 3]
Found solution [2, 1, 1]
Found solution [2, 2]
Found solution [3, 1]

As you can see, this gets this result because it considers solutions like [1, 1, 2] [1, 2, 1] and [2, 1, 1] to be distinct.

Upvotes: 1

Related Questions