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.
Its like, what you do for, finding the number of subsets of a set. Whether an element belongs to your set or it doesn't.
Here, either you use the last coin (in your set of given coins) to make change or you dont.
In case you dont use the last (say 'm'th) coin, now you are left with the subproblem of solving the toatal amount('sum' variable here) using onle the remaining 'm-1' coins ([0:m-2] in the array). We cant use the 'm'th coin because by our own assumption, its not part of the subproblem.
In case you use the last coin, you have the subproblem of solving "sum-Value('m'th coin)" using all the 'm' coins ( because using the 'm' th coin once doesnt bar you from using it again).
Finally you can add the count from both the cases as either of them are a possibility in your final solution.
Lemme know if this helped!!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
Its like, what you do for, finding the number of subsets of a set. Whether an element belongs to your set or it doesn't.
Here, either you use the last coin (in your set of given coins) to make change or you dont.
In case you dont use the last (say 'm'th) coin, now you are left with the subproblem of solving the toatal amount('sum' variable here) using onle the remaining 'm-1' coins ([0:m-2] in the array). We cant use the 'm'th coin because by our own assumption, its not part of the subproblem.
In case you use the last coin, you have the subproblem of solving "sum-Value('m'th coin)" using all the 'm' coins ( because using the 'm' th coin once doesnt bar you from using it again).
Finally you can add the count from both the cases as either of them are a possibility in your final solution.
Lemme know if this helped!!