Coin Combinations I

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct 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 8 ways:

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

Example:

Input:  n = 3, m = 9, a = {2, 3, 5}
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int coinCombinationsI(int n, int m, vector<int> &a)
{

    vector<int> dp(m + 1);
    dp[0] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i - a[j] >= 0)
            {
                dp[i] = (dp[i] + dp[i - a[j]]) % MOD;
            }
        }
    }
    return dp[m];
}

int main()
{

    int n = 3, m = 9;

    vector<int> a = {2, 3, 5};

    cout << coinCombinationsI(n, m, a) << "\n";

    return 0;
}