Coin change problem
This question has been asked a lot in interviews and is one of the classical dynamic programming questions.
Problem statement : Given a bunch of coins of various denominations, find out the number of ways they can sum up to a given value. Assume that there’s an infinite number of each coin available.
For example:
Denominations = {1, 2, 3} and Sum = 4. Possible ways = {1, 1, 1, 1}, {1, 2, 1}, {1, 3}, {2, 2}.
Without going into any more details, I am just going to give you the code on how to do that using:
Brute force
Memoization (top-down)
Tabulation (bottom-up)
LINK to the code.
If you have any questions, do let me know in the comments section.
Happy coding!