Coderust: Hacking the Coding Interview/

...

/

Coin Changing Problem

Coin Changing Problem

Given available coin denominations, find the number​ of ways to make the change for a given amount of money.

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 ...

Access this course and 1400+ top-rated courses and projects.