Coin Combinations II

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

Example:

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

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

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

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

int main()
{
    int n = 3, m = 9;

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

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

    return 0;
}