We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
As you keep on propagating... all of the permutations that end up negative are invalid combinations. all of the permutations that end up exactly at 0 are good combinations.
this is a simplistic approach but it's not correct. Because it doesn't differentiate between... [2,2,5] and [5,2,2]. To get only unique combinations you need to remove 1 element from the C set everytime you iterate.
Finally... what made the cache problematic was that you can't just save values for any given n. You have to save values for n BASED on the C subArray you used to calculate it.
Since the problem states that all values of c are unique, I used the first element of the c subarray as a key which pointed to its own n+1 array.
So for example, the cache could differentiate between running (5, [1,2,3]) and (5, [2,3])
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
Imagine it like a tree....
let's say we have n = 25 and c = [1,2,3]
we can break it down from 25 into 3 branches by:
25 = 1 + f(24)
25 = 2 + f(23)
25 = 3 + f(22)
each of these scenarios also branch off:
f(24) = 1 + f(23)
f(24) = 2 + f(22)
f(24) = 3 + f(21)
f(23) = 1 + f(22)
f(23) = 2 + f(21)
f(23) = 3 + f(20)
f(22) = 1 + f(21)
f(22) = 2 + f(20)
f(22) = 3 + f(19)
As you keep on propagating... all of the permutations that end up negative are invalid combinations. all of the permutations that end up exactly at 0 are good combinations.
this is a simplistic approach but it's not correct. Because it doesn't differentiate between... [2,2,5] and [5,2,2]. To get only unique combinations you need to remove 1 element from the C set everytime you iterate.
so... it'll look like this (in pseudo code).
Since the problem states that all values of c are unique, I used the first element of the c subarray as a key which pointed to its own n+1 array.
So for example, the cache could differentiate between running (5, [1,2,3]) and (5, [2,3])
f(5,[1,2,3]) = 4 (1,1,1,1,1), (1,1,1,2), (1,1,3), (2, 3) f(5,[2,3]) = 1 (2,3)
I hope this helps everyone. I didn't want to give the full answer away. Good luck!