Search⌘ K
Home
Courses
Coderust: Hacking the Coding Interview

Coin Changing Problem

Explore how to solve the coin changing problem by applying dynamic programming. Understand how to build a solution array to count combinations of coins that add to a target amount, optimize your approach to avoid redundant calculations, and improve efficiency in time and space complexity.

We'll cover the following...

Statement

Given an integer array representing coins of different denominations and an integer amount representing a total amount of money, return the number of ways the coins can sum up to the amount.

There is no limit on the number of coins available to you.

Example

Suppose the available coin denominations are 11, 22 and 55 and the total amount of money is 77. We can make the change for 77 in the following six ways:

g d Denominations   1, 2, 5 Amount 7 No. of ways to make the change     1, 1, 1, 1, 1, 1, 1 1, 1, 1, 1, 1, 2 1, 1, 1, 2, 2 1, 2, 2, 2 1, 1, 5 2, 5 Total Methods 6

Sample input

([1, 2, 5], 7)

Expected output

6

Try it yourself

#include <iostream>
#include <vector>
using namespace std;
int SolveCoinChange(vector<int>& denominations, int amount) {
	// TODO: Write - Your - Code
	return -1;
}

Naive solution

A naïve solution would be to generate all subsets of coin denominations that sum up to the required amount. This, however, would require us to generate SnS^{n} subsets, where SS is the required sum, and nn ...