Statement

Suppose you are given a list of coins and a certain amount of money. Each coin in the list is unique and of a different denominationA denomination is a unit of classification for the stated or face value of financial instruments such as currency notes or coins.. You are required to count the number of ways the provided coins can sum up to represent the given amount. If there is no possible way to represent that amount, then return 0.

Note: You may assume that for each combination you make, you have an infinite number of each coin. In simpler terms, you can use a specific coin as many times as you want.

Let's say you have only two coins, $10$ and $20$ cents, and you want to represent the total amount of $30$ cents using these coins. There are only two ways to do this, you can use either of the following combinations:

3 coins of $10$ cents: $10+10+10=30$ .
1 coin of $10$ cents and 1 coin of $20$ cents: $10+20=30.$

Constraints:

1 <= coins.length <= 70
1 <= coins[i] <= 5000
All the coins have a unique value.
0 <= amount <= 5000

Examples

Let's see a few more examples to get a better understanding of the problem statement:

Press + to interact

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Unbounded Knapsack dynamic programming pattern.

Naive approach

A naive approach to solve this problem would be to make all the possible combinations of coins or generate all subsets of coin denominations that sum up to the required amount.

While making the combinations, a point to keep in mind is that we should try to avoid repeatedly counting the same combinations. For example, $10+20$ cents add up to $30$ cents, and so do $20+10$ . In the context of combinations, both these sequences are the same, and we will count them as one combination. We can achieve this by using a subset of coins every time we consider them for combinations. The first time, we can use all $n$ coins, the second time, we can use $n−1$ coins, that is, by excluding the largest one, and so on. This way, it is not possible to consider the same denomination more than once.

As a base case, we return $1$ when the target amount is zero because there is only one way to represent zero irrespective of the number and kinds of coins available. Similarly, for the second base case, if at any point during our search for combinations, the remaining value needed to reach the total amount becomes less than zero, we return $0$ .

The slides below will help you visualize the process.

// Importing required functions
import java.util.*;
import java.util.stream.*;
class CountingWays {
	public static long countWaysRec(int[] coins, int amount, int maximum) {
		// base case 1
		if (amount == 0) return 1;
		// base case 2
		if (amount < 0) return 0;
		
		long ways = 0;
		// iterate over coins
		for (int i = 0; i<coins.length; i++) {
			// to avoid repetition of similar sequences, use coins smaller than maximum 
			if (coins[i] <= maximum && amount - coins[i] >= 0)
				//notice how maximum is set to the current value of coin in recursive call
				ways += countWaysRec(coins, amount - coins[i], coins[i]);
		}
		return ways;
	}
  
	public static long countWays(int[] coins, int amount) {
		int max = Arrays.stream(coins).max().getAsInt();
		return countWaysRec(coins, amount, max);
	}
	// helper function to print an array
	public static String printArrays(int[] arr) {
		String res = "[";
		for (int i : arr) {
			res = res + i + ", ";
		}
		
		return res.substring(0, res.length() - 2) + "]";
	}
	// Driver code
	public static void main(String[] args) {
		int[][] coinsLists = {{7}, {1, 2, 5}, {10}, {49, 233, 96, 132, 188}, 
							  {310, 278, 99, 326, 5, 575, 569, 15, 141, 54},
							  {2823, 4551, 1750, 49, 3256, 405, 380, 4785, 3893, 874},
							  {17, 1422, 30, 1153, 1275}, {1460}, {9, 10, 11}};
	
		int[] amounts = {9, 5, 10, 225, 350, 3200, 700, 2000, 0};
         
		// You can uncomment the lines below and check how this recursive solution causes a time-out
		
		// int[][] temp1 = Arrays.copyOf(coinsLists, coinsLists.length + 1);
        // temp1[coinsLists.length] = new int[]{595, 4610, 3541, 3260, 2008, 2065, 2769, 1437, 1243, 2545, 4053, 2654, 486, 2217, 4860, 4774, 4382, 3402, 46, 1914, 1962, 310, 2442, 798, 1553, 3446, 3507, 4541, 2484, 3718, 135, 2093, 3021, 4159, 3827, 28, 1223, 2358, 2229, 2466, 4903, 1281, 882, 1151, 4262, 1504, 1687, 3643, 668, 1733, 1319, 2630, 2806, 3762, 4191, 121, 2970, 2697, 4662, 453, 2177, 559, 3310, 960, 480, 2899, 989, 1704, 256, 3218};
		// coinsLists = temp1;
		// int[] temp2 = Arrays.copyOf(amounts, amounts.length + 1);
		// temp2[amounts.length] = 5000;
		// amounts = temp2;
		for (int i = 0; i<coinsLists.length; i++) {
			long numWays = countWays(coinsLists[i], amounts[i]);
			System.out.println(i + 1 + ".\tcoins: " + printArrays(coinsLists[i]) + 
									   "\n\tamount: " + amounts[i] +
									   "\n\n\tNumber of Ways: " + numWays);
			Stream.generate(() -> "-").limit(100).forEach(System.out::print);
			System.out.println(" ");
		}
	}
}

Coin Change II using recursion

No.	Coins	Amount	Number of ways
1	[1, 2, 5]	7	6
2	[1, 5, 10, 25]	10	4
3	[7]	9	0
4	[9,10,11]	0	1

Getting Started

0/1 Knapsack

Unbounded Knapsack

Recursive Numbers

Longest Common Substring

Palindromic Subsequence

Conclusion

Coin Change II

Statement

Examples

Try it yourself

Solution

Naive approach

Time complexity