Given a target amount and a set of denominations (coins), find the total number of ways the given target amount can be expressed by using the denominations provided. Consider you have an infinite supply of each denomination given in the array.
Input
target = 10, coins = [1, 5, 10, 25]
Output
4
To get the target sum of 10, we can have multiple ways of adding the given denominations. Those 4 ways are:
1 coin, 10 times.1 coin, 5 times AND 5 coin, 1 time.5 coin, 2 times.10 coin, ` time.Click to reveal
Classic dynamic programming question. Can you try using some sort of array that will keep track of the ways that we are going to use?
Click to reveal
Can you make use of an array that will be the size of the target. Every index will represent a value or a sub-target that can be achieved using the information acquired previously.