Coin Change Problem with DP and Recursion

Outline of Article

Naive approach - Brute Force Recursion
Pro Approach - Dynamic Programming & Recursion [Optimal Time Complexity]

All codes are in C++, Java, and Python.

Introduction

Problem: Given a set of coins and a value 'V'. Find the number of ways

we can make a change of 'V'.

You are given an array of coins of size n, each representing a coin of a distinct denomination. Target is another value that you are given. Discover the various combinations that make up the desired quantity. Consider that there are endless quantities of each type of coin.

Ex : Problem: S = {1,2,3} V = 3

Possible ways to make change are; {3}, {2,1}, {1,1,1}

Note: {1,2} are not counted as separate as it is the same as {2,1}

Naive Approach - Exponential Complexity

We can use a brute force recursion to fix this issue crudely. We can try every conceivable combination of taking coins to equal the desired amount, adding them all up to determine how many ways there are to get the desired amount.
The simplest scenario would be when we have no coins or when the goal is to reach zero.
Time Complexity: O(targetn) // Exponential
Space Complexity: O(targetn) // Exponential

int coinChange(vector<int> &coins, int n, int target) {
if(target == 0) {
return 1;
}
if(target < 0) {
return 0;
}
if(n <= 0 && target > 0) {
return 0;
}
return coinChange(coins, n - 1, target) + coinChange(coins, n, target - coins[n - 1]);
}
int numberOfCombinations(vector<int> &coins, int target) {
int n = coins.size();
return coinChange(coins, n, target);
}

Naive approach ends here. We will now learn the pro approach using DP and Recursion

write your code here: Coding Playground

Pro Approach - O(n) complexity

Dynamic programming allows us to find a pseudo-polynomial-time solution to this issue.
You'll see that the coin change() function performs a lot of recursive calls for the same parameter. So that the same function call is not made repeatedly, we memoize the function calls using a DP array.
The number of ways we can reach the desired amount j using the first provided denominations is represented by DP[i][j] in our DP array in this case.
Time Complexity: O(n * target)
Space Complexity: O(n * target)

Dynamic Programming

vector<vector<int>> dp;
int coinChange(vector<int> &coins, int n, int target) {
if(target == 0) {
return 1;
}
if(target < 0) {
return 0;
}
if(n <= 0 && target > 0) {
return 0;
}
if(dp[n][target] != -1) {
return dp[n][target];
}
return dp[n][target] = coinChange(coins, n - 1, target) +
coinChange(coins, n, target - coins[n - 1]);
}
int numberOfCombinations(vector<int> &coins, int target) {
int n = coins.size();
vector<vector<int>> temp(n + 1, vector<int> (target + 1, -1));
dp = temp;
return coinChange(coins, n, target);
}

ANOTHER C++ CODE

int numberOfCombinations(vector<int> coins, int target) {
int n = coins.size();
int dp[n + 1][target + 1];
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= target; j++) {
if(i == 0) {
dp[i][j] = 0;
} else if(j == 0) {
dp[i][j] = 1;
} else {
if(j - coins[i - 1] >= 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[n][target];
}

write your code here: Coding Playground

Python Code : Dynamic Programming

def numberOfCombinations(coins, target):
n = len(coins)
dp = [[0 for j in range(target + 1)] for i in range(n + 1)]
for i in range(n + 1):
for j in range(target + 1):
if i == 0:
dp[i][j] = 0
elif j == 0:
dp[i][j] = 1
else:
if j - coins[i - 1] >= 0:
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][target]

This code is solving the coin change problem, by counting the number of ways of making change for a given amount using a given set of coin denominations. The function takes in two arguments: a list of coins and an target. It uses a 2D array dp and fills it using the bottom-up approach, also known as dynamic programming. The function returns the number of combinations of coins that can be used to make changes for the given target.

You would call the function like this:

numberOfCombinations([1, 2, 3], 4)

write your code here: Coding Playground

Java Code: Dynamic Programming

public int numberOfCombinations(int[] coins, int target) {
int n = coins.length;
int[][] dp = new int[n + 1][target + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= target; j++) {
if (i == 0) {
dp[i][j] = 0;
} else if (j == 0) {
dp[i][j] = 1;
} else {
if (j - coins[i - 1] >= 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[n][target];
}

Call function like this:

int result = numberOfCombinations(new int[]{1, 2, 3}, 4);

write your code here: Coding Playground

Consider the problem of making change for a smaller amount and add a coin of the largest denomination that is less than or equal to the remaining amount. Here is an example of a Python function that solves the coin exchange problem.

Recursion

def make_change(amount, denominations):
if amount == 0:
return []
if len(denominations) == 0:
return None
if denominations[0] > amount:
return make_change(amount, denominations[1:])
use_it = make_change(amount - denominations[0], denominations)
if use_it != None:
return [denominations[0]] + use_it
lose_it = make_change(amount, denominations[1:])
if lose_it == None:
return None
if use_it == None:
return lose_it
return min(use_it, lose_it, key=len)

Explanation for the code:

This function takes in two arguments: an amount to make change for and a list of denominations of coins. It uses recursion to consider two possibilities: using the largest coin denomination or not using it, and returns the solution with the fewest number of coins.

You would call the function like this:

make_change(100, [1, 5, 10, 25])

write your code here: Coding Playground

Here the dynamic programming code ends. now we will learn the coin exchange problem using recursion with optimal time complexity.

C++ Code: Recursion

#include <vector>
#include <algorithm>

std::vector<int> make_change(int amount, std::vector<int> denominations) {
if (amount == 0) {
return {};
}
if (denominations.empty()) {
return {};
}
if (denominations[0] > amount) {
return make_change(amount, std::vector<int>(denominations.begin() + 1, denominations.end()));
}
auto use_it = make_change(amount - denominations[0], denominations);
if (!use_it.empty()) {
use_it.push_back(denominations[0]);
return use_it;
}
auto lose_it = make_change(amount, std::vector<int>(denominations.begin() + 1, denominations.end()));
if (use_it.empty() && lose_it.empty()) {
return {};
}
if (use_it.empty() || (lose_it.size() < use_it.size())) {
return lose_it;
}
return use_it;
}

Call the Function like this:

std::vector<int> result = make_change(100, {1, 5, 10, 25});

It will return the vector of coin denomination which makes change for 100.

Note that in C++, you will have to include <vector> and <algorithm> to use vector and min functions respectively.

write your code here: Coding Playground

Here is an example of a Java function that solves the coin exchange problem using recursion:

import java.util.ArrayList;
import java.util.List;

public class CoinExchange {
public static List<Integer> makeChange(int amount, int[] denominations) {
if (amount == 0) {
return new ArrayList<Integer>();
}
if (denominations.length == 0) {
return new ArrayList<Integer>();
}
if (denominations[0] > amount) {
int[] newDenominations = new int[denominations.length - 1];
for (int i = 1; i < denominations.length; i++) {
newDenominations[i-1] = denominations[i];
}
return makeChange(amount, newDenominations);
}
List<Integer> useIt = makeChange(amount - denominations[0], denominations);
if (!useIt.isEmpty()) {
useIt.add(denominations[0]);
return useIt;
}
List<Integer> loseIt = makeChange(amount, new int[denominations.length - 1]);
if (useIt.isEmpty() && loseIt.isEmpty()) {
return new ArrayList<Integer>();
}
if (useIt.isEmpty() || (loseIt.size() < useIt.size())) {
return loseIt;
}
return useIt;
}
}

You call the function like this :

List<Integer> result = CoinExchange.makeChange(100, new int[]{1, 5, 10, 25});

It will return the list of coin denomination which makes change for 100.

Note that in this code, I have used ArrayList and Integer.

write your code here: Coding Playground