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:

1. Brute force

2. Memoization (top-down)

3. Tabulation (bottom-up)

LINK to the code.

If you have any questions, do let me know in the comments section.

Happy coding!