#include <stdio.h>
#include <string.h>
// create lookup matrix of size [n+1][N+1]
int lookup[4][5];
// 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;
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (lookup[n][N] == -1)
{
// Case 1. include current coin S[n] in solution and recurse
// 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 recurse
// for remaining coins (n - 1)
int exclude = count(S, n - 1, N);
// assign total ways by including or excluding current coin
lookup[n][N] = include + exclude;
}
// return solution to current sub-problem
return lookup[n][N];
}
// Coin Change Problem
int main(void)
{
// n coins of given denominations
int S[] = { 1, 2, 3 };
int n = sizeof(S) / sizeof(S[0]);
// Total Change required
int N = 4;
// initialize lookup matrix by -1
memset(lookup
, -1, sizeof(lookup
)); printf("Total number of ways to get desired change is %d", count(S, n - 1, N));
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCi8vIGNyZWF0ZSBsb29rdXAgbWF0cml4IG9mIHNpemUgW24rMV1bTisxXQppbnQgbG9va3VwWzRdWzVdOwoKLy8gRnVuY3Rpb24gdG8gZmluZCB0aGUgdG90YWwgbnVtYmVyIG9mIGRpc3RpbmN0IHdheXMgdG8gZ2V0IGNoYW5nZSBvZiBOCi8vIGZyb20gdW5saW1pdGVkIHN1cHBseSBvZiBjb2lucyBpbiBzZXQgUwppbnQgY291bnQoaW50IFNbXSwgaW50IG4sIGludCBOKQp7CiAgICAvLyBpZiB0b3RhbCBpcyAwLCByZXR1cm4gMSAoc29sdXRpb24gZm91bmQpCiAgICBpZiAoTiA9PSAwKQogICAgICAgIHJldHVybiAxOwoKICAgIC8vIHJldHVybiAwIChzb2x1dGlvbiBkbyBub3QgZXhpc3QpIGlmIHRvdGFsIGJlY29tZSBuZWdhdGl2ZSBvcgogICAgLy8gbm8gZWxlbWVudHMgYXJlIGxlZnQKICAgIGlmIChOIDwgMCB8fCBuIDwgMCkKICAgICAgICByZXR1cm4gMDsKCiAgICAvLyBpZiBzdWItcHJvYmxlbSBpcyBzZWVuIGZvciB0aGUgZmlyc3QgdGltZSwgc29sdmUgaXQgYW5kCiAgICAvLyBzdG9yZSBpdHMgcmVzdWx0IGluIGEgbWFwCiAgICBpZiAobG9va3VwW25dW05dID09IC0xKQogICAgewogICAgICAgIC8vIENhc2UgMS4gaW5jbHVkZSBjdXJyZW50IGNvaW4gU1tuXSBpbiBzb2x1dGlvbiBhbmQgcmVjdXJzZQogICAgICAgIC8vIHdpdGggcmVtYWluaW5nIGNoYW5nZSAoTiAtIFNbbl0pIHdpdGggc2FtZSBudW1iZXIgb2YgY29pbnMKICAgICAgICBpbnQgaW5jbHVkZSA9IGNvdW50KFMsIG4sIE4gLSBTW25dKTsKCiAgICAgICAgLy8gQ2FzZSAyLiBleGNsdWRlIGN1cnJlbnQgY29pbiBTW25dIGZyb20gc29sdXRpb24gYW5kIHJlY3Vyc2UKICAgICAgICAvLyBmb3IgcmVtYWluaW5nIGNvaW5zIChuIC0gMSkKICAgICAgICBpbnQgZXhjbHVkZSA9IGNvdW50KFMsIG4gLSAxLCBOKTsKCiAgICAgICAgLy8gYXNzaWduIHRvdGFsIHdheXMgYnkgaW5jbHVkaW5nIG9yIGV4Y2x1ZGluZyBjdXJyZW50IGNvaW4KICAgICAgICBsb29rdXBbbl1bTl0gPSBpbmNsdWRlICsgZXhjbHVkZTsKICAgIH0KCiAgICAvLyByZXR1cm4gc29sdXRpb24gdG8gY3VycmVudCBzdWItcHJvYmxlbQogICAgcmV0dXJuIGxvb2t1cFtuXVtOXTsKfQoKLy8gQ29pbiBDaGFuZ2UgUHJvYmxlbQppbnQgbWFpbih2b2lkKQp7CiAgICAvLyBuIGNvaW5zIG9mIGdpdmVuIGRlbm9taW5hdGlvbnMKICAgIGludCBTW10gPSB7IDEsIDIsIDMgfTsKICAgIGludCBuID0gc2l6ZW9mKFMpIC8gc2l6ZW9mKFNbMF0pOwoKICAgIC8vIFRvdGFsIENoYW5nZSByZXF1aXJlZAogICAgaW50IE4gPSA0OwoKICAgIC8vIGluaXRpYWxpemUgbG9va3VwIG1hdHJpeCBieSAtMQogICAgbWVtc2V0KGxvb2t1cCwgLTEsIHNpemVvZihsb29rdXApKTsKICAgIHByaW50ZigiVG90YWwgbnVtYmVyIG9mIHdheXMgdG8gZ2V0IGRlc2lyZWQgY2hhbmdlIGlzICVkIiwKICAgICAgICAgICBjb3VudChTLCBuIC0gMSwgTikpOwoKICAgIHJldHVybiAwOwp9Cg==