#include <iostream>
#include <unordered_map>
using namespace std;
// Function to find the total number of ways to get change of N
// from unlimited supply of coins in set S
int count(int S[], int n, int N, auto &lookup)
{
// if total is 0, return 1
if (N == 0)
return 1;
// return 0 if total become negative
if (N < 0)
return 0;
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (lookup.find(N) == lookup.end())
{
// do for each coin
for (int i = 0; i < n; i++)
{
// recurse to see if total can be reached by including
// current coin S[i]
lookup[N] += count(S, n, N - S[i], lookup);
}
}
// return solution to current sub-problem
return lookup[N];
}
// Coin Change Problem
int main()
{
// n coins of given denominations
int S[] = { 1, 2, 3 };
int n = sizeof(S) / sizeof(S[0]);
// Total Change required
int N = 4;
// create a map to store solutions of subproblems
unordered_map<int,int> lookup;
cout << "Total number of ways to get desired change is "
<< count(S, n, N, lookup);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEZ1bmN0aW9uIHRvIGZpbmQgdGhlIHRvdGFsIG51bWJlciBvZiB3YXlzIHRvIGdldCBjaGFuZ2Ugb2YgTgovLyBmcm9tIHVubGltaXRlZCBzdXBwbHkgb2YgY29pbnMgaW4gc2V0IFMKaW50IGNvdW50KGludCBTW10sIGludCBuLCBpbnQgTiwgYXV0byAmbG9va3VwKQp7CiAgICAvLyBpZiB0b3RhbCBpcyAwLCByZXR1cm4gMQogICAgaWYgKE4gPT0gMCkKICAgICAgICByZXR1cm4gMTsKCiAgICAvLyByZXR1cm4gMCBpZiB0b3RhbCBiZWNvbWUgbmVnYXRpdmUKICAgIGlmIChOIDwgMCkKICAgICAgICByZXR1cm4gMDsKCiAgICAvLyBpZiBzdWItcHJvYmxlbSBpcyBzZWVuIGZvciB0aGUgZmlyc3QgdGltZSwgc29sdmUgaXQgYW5kCiAgICAvLyBzdG9yZSBpdHMgcmVzdWx0IGluIGEgbWFwCiAgICBpZiAobG9va3VwLmZpbmQoTikgPT0gbG9va3VwLmVuZCgpKQogICAgewoJICAgIC8vIGRvIGZvciBlYWNoIGNvaW4KCSAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCSAgICB7CgkgICAgICAgIC8vIHJlY3Vyc2UgdG8gc2VlIGlmIHRvdGFsIGNhbiBiZSByZWFjaGVkIGJ5IGluY2x1ZGluZwoJICAgICAgICAvLyBjdXJyZW50IGNvaW4gU1tpXQoJICAgICAgICBsb29rdXBbTl0gKz0gY291bnQoUywgbiwgTiAtIFNbaV0sIGxvb2t1cCk7CgkgICAgfQogICAgfQoKICAgIC8vIHJldHVybiBzb2x1dGlvbiB0byBjdXJyZW50IHN1Yi1wcm9ibGVtCiAgICByZXR1cm4gbG9va3VwW05dOwp9CgovLyBDb2luIENoYW5nZSBQcm9ibGVtCmludCBtYWluKCkKewogICAgLy8gbiBjb2lucyBvZiBnaXZlbiBkZW5vbWluYXRpb25zCiAgICBpbnQgU1tdID0geyAxLCAyLCAzIH07CiAgICBpbnQgbiA9IHNpemVvZihTKSAvIHNpemVvZihTWzBdKTsKCiAgICAvLyBUb3RhbCBDaGFuZ2UgcmVxdWlyZWQKICAgIGludCBOID0gNDsKCgkvLyBjcmVhdGUgYSBtYXAgdG8gc3RvcmUgc29sdXRpb25zIG9mIHN1YnByb2JsZW1zCgl1bm9yZGVyZWRfbWFwPGludCxpbnQ+IGxvb2t1cDsKCQoJY291dCA8PCAiVG90YWwgbnVtYmVyIG9mIHdheXMgdG8gZ2V0IGRlc2lyZWQgY2hhbmdlIGlzICIKICAgICAgICAgICAgPDwgY291bnQoUywgbiwgTiwgbG9va3VwKTsKCiAgICByZXR1cm4gMDsKfQ==