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!

Leave a Reply

Your email address will not be published. Required fields are marked *