#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
// create a map to store solutions of subproblems
unordered_map<string, int> lookup;
 
// Function to find the total number of distinct ways to get change of N
// from unlimited supply of coins in set S
int count(int S[], int n, int N)
{
    // if total is 0, return 1 (solution found)
    if (N == 0)
        return 1;
 
    // return 0 (solution do not exist) if total become negative or
    // no elements are left
    if (N < 0 || n < 0)
        return 0;
 
    // construct an unique map key from dynamic elements of the input
    string key = to_string(n) + "|" + to_string(N);
 
    // if sub-problem is seen for the first time, solve it and
    // store its result in a map
    if (lookup.find(key) == lookup.end())
    {
        // Case 1. include current coin S[n] in solution and recur
        // with remaining change (N - S[n]) with same number of coins
        int include = count(S, n, N - S[n]);
 
        // Case 2. exclude current coin S[n] from solution and recur
        // for remaining coins (n - 1)
        int exclude = count(S, n - 1, N);
 
        // assign total ways by including or excluding current coin
        lookup[key] = include + exclude;
    }
 
    // return solution to current sub-problem
    return lookup[key];
}
 
// Coin Change Problem
int main()
{
    // n coins of given denominations
    int S[] = { 2, 3, 5};
    int n = sizeof(S) / sizeof(S[0]);
 
    // Total Change required
    int N = 9;
 
    cout << "Total number of ways to get desired change is "
        << count(S, n - 1, N);
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHN0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAovLyBjcmVhdGUgYSBtYXAgdG8gc3RvcmUgc29sdXRpb25zIG9mIHN1YnByb2JsZW1zCnVub3JkZXJlZF9tYXA8c3RyaW5nLCBpbnQ+IGxvb2t1cDsKIAovLyBGdW5jdGlvbiB0byBmaW5kIHRoZSB0b3RhbCBudW1iZXIgb2YgZGlzdGluY3Qgd2F5cyB0byBnZXQgY2hhbmdlIG9mIE4KLy8gZnJvbSB1bmxpbWl0ZWQgc3VwcGx5IG9mIGNvaW5zIGluIHNldCBTCmludCBjb3VudChpbnQgU1tdLCBpbnQgbiwgaW50IE4pCnsKICAgIC8vIGlmIHRvdGFsIGlzIDAsIHJldHVybiAxIChzb2x1dGlvbiBmb3VuZCkKICAgIGlmIChOID09IDApCiAgICAgICAgcmV0dXJuIDE7CiAKICAgIC8vIHJldHVybiAwIChzb2x1dGlvbiBkbyBub3QgZXhpc3QpIGlmIHRvdGFsIGJlY29tZSBuZWdhdGl2ZSBvcgogICAgLy8gbm8gZWxlbWVudHMgYXJlIGxlZnQKICAgIGlmIChOIDwgMCB8fCBuIDwgMCkKICAgICAgICByZXR1cm4gMDsKIAogICAgLy8gY29uc3RydWN0IGFuIHVuaXF1ZSBtYXAga2V5IGZyb20gZHluYW1pYyBlbGVtZW50cyBvZiB0aGUgaW5wdXQKICAgIHN0cmluZyBrZXkgPSB0b19zdHJpbmcobikgKyAifCIgKyB0b19zdHJpbmcoTik7CiAKICAgIC8vIGlmIHN1Yi1wcm9ibGVtIGlzIHNlZW4gZm9yIHRoZSBmaXJzdCB0aW1lLCBzb2x2ZSBpdCBhbmQKICAgIC8vIHN0b3JlIGl0cyByZXN1bHQgaW4gYSBtYXAKICAgIGlmIChsb29rdXAuZmluZChrZXkpID09IGxvb2t1cC5lbmQoKSkKICAgIHsKICAgICAgICAvLyBDYXNlIDEuIGluY2x1ZGUgY3VycmVudCBjb2luIFNbbl0gaW4gc29sdXRpb24gYW5kIHJlY3VyCiAgICAgICAgLy8gd2l0aCByZW1haW5pbmcgY2hhbmdlIChOIC0gU1tuXSkgd2l0aCBzYW1lIG51bWJlciBvZiBjb2lucwogICAgICAgIGludCBpbmNsdWRlID0gY291bnQoUywgbiwgTiAtIFNbbl0pOwogCiAgICAgICAgLy8gQ2FzZSAyLiBleGNsdWRlIGN1cnJlbnQgY29pbiBTW25dIGZyb20gc29sdXRpb24gYW5kIHJlY3VyCiAgICAgICAgLy8gZm9yIHJlbWFpbmluZyBjb2lucyAobiAtIDEpCiAgICAgICAgaW50IGV4Y2x1ZGUgPSBjb3VudChTLCBuIC0gMSwgTik7CiAKICAgICAgICAvLyBhc3NpZ24gdG90YWwgd2F5cyBieSBpbmNsdWRpbmcgb3IgZXhjbHVkaW5nIGN1cnJlbnQgY29pbgogICAgICAgIGxvb2t1cFtrZXldID0gaW5jbHVkZSArIGV4Y2x1ZGU7CiAgICB9CiAKICAgIC8vIHJldHVybiBzb2x1dGlvbiB0byBjdXJyZW50IHN1Yi1wcm9ibGVtCiAgICByZXR1cm4gbG9va3VwW2tleV07Cn0KIAovLyBDb2luIENoYW5nZSBQcm9ibGVtCmludCBtYWluKCkKewogICAgLy8gbiBjb2lucyBvZiBnaXZlbiBkZW5vbWluYXRpb25zCiAgICBpbnQgU1tdID0geyAyLCAzLCA1fTsKICAgIGludCBuID0gc2l6ZW9mKFMpIC8gc2l6ZW9mKFNbMF0pOwogCiAgICAvLyBUb3RhbCBDaGFuZ2UgcmVxdWlyZWQKICAgIGludCBOID0gOTsKIAogICAgY291dCA8PCAiVG90YWwgbnVtYmVyIG9mIHdheXMgdG8gZ2V0IGRlc2lyZWQgY2hhbmdlIGlzICIKICAgICAgICA8PCBjb3VudChTLCBuIC0gMSwgTik7CiAKICAgIHJldHVybiAwOwp9