Coin Change Problem: Dynamic Programming

Hacking the coding interviews at FAANG!

Problem Statement: Given a number array to represent different coin denominations and a total amount ‘T’, we need to find all the different ways to make a change for ‘T’ with the given coin denominations. We can assume an infinite supply of coins, therefore, each coin can be chosen multiple times.

Note: This problem follows the Unbounded Knapsack pattern of Dynamic Programming.

Solution 1: Recursive Approach

A basic brute-force solution could be to try all combinations of the given coins to select the ones that give a total sum of ‘T’. This is what our algorithm will look like:

for each coin 'c'
create a new set which includes one quantity of coin 'c' if it does not exceed 'T', and
recursively call to process all coins
create a new set without coin 'c', and recursively call to process the remaining coins
return the count of sets who have a sum equal to 'T'

Code (JavaScript)

let countChange = function(denominations, total) {
function countChangeRecursive(denominations, total, currentIndex) {
// base checks
if (total === 0) return 1;
if (denominations.length === 0 || currentIndex >= denominations.length) {
return 0;
}
// recursive call after selecting the coin at the currentIndex
// if the coin at currentIndex exceeds the total, we shouldn't process this
let sum1 = 0;
if (denominations[currentIndex] <= total) {
sum1 = countChangeRecursive(denominations, total - denominations[currentIndex], currentIndex);
}
// recursive call after excluding the coin at the currentIndex
const sum2 = countChangeRecursive(denominations, total, currentIndex + 1);
return sum1 + sum2;
}
return countChangeRecursive(denominations, total, 0);
};

The time complexity of the above algorithm is exponential O(2^{C+T}), where ‘C’ represents total coin denominations and ‘T’ is the total amount that we want to make change.

The space complexity will be O(C+T).

Let’s try to find a better solution.

Solution 2: Top-down Dynamic Programming with Memoization

We can use memoization to overcome the overlapping sub-problems. We will be using a two-dimensional array to store the results of solved sub-problems. As mentioned above, we need to store results for every coin combination and for every possible sum:

let countChange = function(denominations, total) {
const dp = [];
function countChangeRecursive(denominations, total, currentIndex) {
// base checks
if (total === 0) return 1;
if (denominations.length === 0 || currentIndex >= denominations.length) {
return 0;
}
dp[currentIndex] = dp[currentIndex] || [];
// if we have already processed a similar sub-problem, return the result from memory
if (typeof dp[currentIndex][total] !== 'undefined') return dp[currentIndex][total];
// recursive call after selecting the coin at the currentIndex
// if the number at currentIndex exceeds the total, we shouldn't process this
let sum1 = 0;
if (denominations[currentIndex] <= total) {
sum1 = countChangeRecursive(denominations, total - denominations[currentIndex], currentIndex);
}
// recursive call after excluding the number at the currentIndex
const sum2 = countChangeRecursive(denominations, total, currentIndex + 1);
dp[currentIndex][total] = sum1 + sum2;
return dp[currentIndex][total];
}
return countChangeRecursive(denominations, total, 0);
};

Will discuss for coding interview problems in the upcoming stories.