CSES - Shared codeLink to this code:
https://cses.fi/paste/753f06b17cbe2b761640d5/
// Coin Combinations I
#include<bits/stdc++.h>
using namespace std;
#define int long long
int M = 1e9 + 7;
int go(int x, int n, int a[]) {
int dp[x + 1];
for(int i = 0; i <= x; i++) dp[i] = 0;
dp[0] = 1;
for(int j = 1; j <= x; j++) {
for(int i = 0; i < n; i++) {
if(j >= a[i]) {
dp[j] += dp[j - a[i]];
}
}
dp[j] %= M;
}
return dp[x];
}
signed main() {
int n, x;
cin >> n >> x;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = go(x, n, a);
if(ans == INT_MAX) {
cout << -1;
} else {
cout << ans;
}
return 0;
}