Number Of Ways To Make Change

Category: Dynamic Programming

```

Problem Statement

Number Of Ways To Make Change Given an array of positive integers representing coin denominations and a single non-negative integer n representing a target amount of money, write a function that returns the number of ways to make change for that target amount using the given coin denominations. Note that an unlimited amount of coins is at your disposal. Sample Input n = 6 denoms = [1, 5] Sample Output // 1x1 + 1x5 and 6x1 Hints Hint 1 Try building an array of the number of ways to make change for all amounts between 0 and n inclusive. Note that there is only one way to make change for 0: that is to not use any coins. Hint 2 Build up the array mentioned in Hint #1 one coin denomination at a time. In other words, nd the number of ways to make change for all amounts between 0 and n with only one denomination, then with two, etc., until you use all denominations. Optimal Space & Time Complexity O(nd) time | O(n) space - where n is the target amount and d is the number of coin denominations

```

Approach & Solution

Solution 1

```java class Program { // O(nd) time | O(n) space public static int numberOfWaysToMakeChange(int n, int[] denoms) { int[] ways = new int[n + 1]; ways[0] = 1; for (int denom : denoms) { for (int amount = 1; amount < n + 1; amount++) { if (denom <= amount) { ways[amount] += ways[amount - denom]; } } } return ways[n]; } }

```

Test Cases

``` Video Solution Video Solution

``` Test Case 1 {"n": 6, "denoms": [1, 5]} Test Case 2 {"n": 0, "denoms": [2, 3, 4, 7]} Test Case 3 {"n": 9, "denoms": [5]} Test Case 4 {"n": 7, "denoms": [2, 4]} Test Case 5 {"n": 4, "denoms": [1, 5, 10, 25]} Test Case 6 {"n": 5, "denoms": [1, 5, 10, 25]} Test Case 7 {"n": 10, "denoms": [1, 5, 10, 25]} Test Case 8 {"n": 25, "denoms": [1, 5, 10, 25]} Test Case 9 {"n": 12, "denoms": [2, 3, 7]} Test Case 10 {"n": 7, "denoms": [2, 3, 4, 7]}