Why am i getting a test case wrong in coin change dynamic programming approach?

Question

I am trying to solve coin change problem using dynamic programming approach. What i have done is used a less space consuming one. Here goes my code:

 #include <cmath>
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 int coinchange(int S[],int m,int n){
 long long table[n+1];

 // Initialize all table values as 0
memset(table, 0, sizeof(table));

// Base case (If given value is 0)
table[0] = 1;

// Pick all coins one by one and update the table[] values
// after the index greater than or equal to the value of the
// picked coin
for(int i=0; i<m; i++)
    for(int j=S[i]; j<=n; j++)
        table[j] += table[j-S[i]];

return table[n];
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
int nn,mm,ar[250];
cin>>mm>>nn;
for(int i=0;i<nn;i++)
    cin>>ar[i];
long long c=coinchange(ar,nn,mm);
cout<<c;
return 0;
}

it is showing wrong answer for the following test case: input: 250 24 41 34 46 9 37 32 42 21 7 13 1 24 3 43 2 23 8 45 19 30 29 18 35 11 expected output: 15685693751

Answer 1

The code is correct. You are just returning an 'int' instead of 'long long' from your coinchange function. Everything else is correct. Try to debug your code by printing the intermediate values. It helps you in understanding your code better for future.