“The sea’s only gifts are harsh blows, and occasionally the chance to feel strong. Now I don’t know much about the sea, but I do know that that’s the way it is here. And I also know how important it is in life not necessarily to be strong but to feel strong. To measure yourself at least once. To find yourself at least once in the most ancient of human conditions. Facing the blind deaf stone alone, with nothing to help you but your hands and your own head.”

~Christopher McCandless

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!