Counting Change Combinations

Write a function that counts how many different ways you can make change for an amount of money, given an array of coin denominations. For example, there are 3 ways to give change for 4 if you have coins with denomination 1 and 2:

1
1+1+1+1, 1+1+2, 2+2.

The order of coins does not matter. Also, assume that you have an infinite amount of coins.

Solution

Recursion

Optimal Substructure

To count total number solutions, we can divide all set solutions in two sets.

  1. Solutions that do not contain ith coin (or coins[i]).
  2. Solutinos that contain at least one coins[i].

Let count(coins[], money, index) be the function to count the number of solutions, then it can be written as sum of count(coins[], money, index) and count(coins[], money - coins[index], index).

Overlapping Subproblems and Implementation

Following is a simple recursive implementation of the Coin Change problem. The implementation simply follows the recursive structure mentioned above.

1
2
3
4
5
var countChange = function(coins, money, index = coins.length - 1) {
if (money === 0) return 1
if (money < 0 || index < 0) return 0
return countChange(coins, money, index - 1) + countChange(coins, money - coins[index], index)
}

Dynamic Programming

Since same subproblems are called ageain, this problem has Overlapping Subprolems property. So the Coin Change problem has both properties of a dynamic programming problem. Like other typical DP problems, recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in bottom up manner.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var countChange = function(coins, money) {
var m = money, n = coins.length
var dp = Array(m + 1).fill().map(() => Array(n).fill(0))
// Fill the entries for money = 0
for (var i = 0; i < n; i++)
dp[0][i] = 1

for (var i = 1; i <= m; i++) {
for (var j = 0; j < n; j++) {
// Count of solutions inculding coins[j]
var x = i - coins[j] >= 0 ? dp[i - coins[j]][j] : 0
// Count of solutions excluding coins[j]
var y = j > 0 ? dp[i][j - 1] : 0
dp[i][j] = x + y
}
}
return dp[m][n-1]
}

The space optimized version:

1
2
3
4
5
6
7
8
9
10
11
var countChange = function(coins, money) {
var dp = Array(money + 1).fill(0)
dp[0] = 1

for (var i = 0; i < coins.length; i++) {
for (var j = coins[i]; j <= money; j++) {
dp[j] += dp[j - coins[i]]
}
}
return dp[money]
}
0%