How can I count distinct combinations in coin change?

Question

long long num(long long p)
{
   if(p<0)
      return 0;
   if(p==0)
      return 1;
   if(t[p]!=0)
      return t[p];
   t[p]=num(p-1)+num(p-2)+num(p-5)+num(p-10)+num(p-20)+num(p-50)+num(p-100);
   return t[p];
}

I use this method num to count number of possible ways of coin change problem.The problem is this approach counts 1,1,2 and 1,2,1 as different which should be taken as 1 .How to do that? Cant find any good solution anywhere.

You should probably try [math.stackexchange.com](https://math.stackexchange.com/) — Aditi Rawat, Dec 22 '17 at 21:19
You just need to remember `lastUsedCoinIndex` and consider only coin indexes greater or equal. See here : https://stackoverflow.com/questions/46257659/python-coin-change-dynamic-programming/46261706#46261706 — รยקคгรђשค, Dec 24 '17 at 20:32

score 0 · Answer 1 · answered Dec 22 '17 at 21:24

0

This is a C++ implementation of the number of distinct coin combos.

int combo(int d[], int r, int R)
{
    if (R == 0)
        return 1;
    if (R < 0)
        return 0;

    int tot = 0;

    for (int i = 0; i < r; i++) 
        tot += combo(d, r, R - d[i]);

    return tot;
}

Hope this helps.

answered Dec 22 '17 at 21:24

Jake Freeman

1,700
1
8
15

But this is exactly same as my code except you used a for loop .This will count 1,1,2 and 1,2,1 as two different possibilities what i want is them to be counted as 1. – Aditya Upadhyay Dec 23 '17 at 06:03

How can I count distinct combinations in coin change?

1 Answers1