-2

I am solving the coin combination problem given below:

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

  • 2+2+5
  • 3+3+3
  • 2+2+2+3

Input:

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c1,c2,…,cn: the value of each coin.

Output:

Print one integer: the number of ways modulo 109+7.

For more information here is the link to the given problem: https://cses.fi/problemset/task/1636

I tried writing the following code in C++ using dynamic programming:

#include<bits/stdc++.h>
using namespace std;
 
const long N=1e6+10,mod=1e9+7;
long dp[N];
 
long recursion(int coins,int sum,int a[])
{
    if(sum==0)
        return 1;
    if(dp[sum]!=-1)
        return dp[sum];
    long count=0;
    for(long i=0;i<coins;i++)
    {
        if(sum-a[i]>=0)
            count=count+recursion(coins,sum-a[i],a);
    }
    return dp[sum]=count%mod;
} 
 
int main()
{
    memset(dp,-1,sizeof(dp));
    int n,x;
    cin>>n>>x;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<recursion(n,x,a);
    return 0;
}

But it shows wrong answer for some test cases. Can someone please help me sort this problem.

Wyck
  • 8,140
  • 4
  • 39
  • 51
tdcoder
  • 1
  • 2
  • 1
    Welcome to Stack Overflow! It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) – NathanOliver May 16 '22 at 15:13
  • 1
    I recommend you get out of the habit of using [`using namespace std;`](https://stackoverflow.com/q/1452721/10077) and [`#include `](https://stackoverflow.com/q/31816095/10077). They're bad individually, but especially insidious together. – Fred Larson May 16 '22 at 15:16
  • You're overflowing; you need to pay attention to "modulo 10^9+7". Read about modular arithmetic and the `%` operator in your favourite C++ book. – molbdnilo May 16 '22 at 15:39
  • 1
    `memset(dp,-1,sizeof(dp));` -- Don't do this. The `memset` is for copying bytes, not for setting an array to a specific integer value. Then `int n,x; cin>>n>>x; int a[n];` -- This is not valid C++, as arrays must have their sizes denoted by a compile-time constant, not a runtime value. Instead, use `std::vector a(n);`. And then this lazy hack: `const long N=1e6+10; long dp[N]` -- What if the number of data is 10?. You've wasted 999990 elements for nothing. ;Bottom line -- don't use competitive coding websites if your goal is to learn C++ properly. – PaulMcKenzie May 16 '22 at 15:49
  • 1
    "not working" is not a sufficiently detailed description of the problem. "wrong answer for some test cases" would be a lot more helpful if you showed the test cases that failed, along with expected and actual results. – Wyck May 16 '22 at 15:51

0 Answers0