Problem Statement

Coin Combinations I

Implementation


void solve()
{
    ll n, x;
    cin >> n >> x;

    vll c(n);
    rep(i, n) cin >> c[i];

    vll dp(x + 1, 0);
    dp[0] = 1;

    FOR(i, 1, x)
    {
        rep(j, n)
        {
            if (i - c[j] >= 0)
            {
                dp[i] += dp[i - c[j]];
                dp[i] %= mod;
            }
        }
    }
    if (dp[x] == inf)
        cout << -1;
    else
        cout << dp[x];
}