coin combinations 1 cses solution
#include <bits/stdc++.h>using namespace std;using ll = long long;using vi = vector<int>;#define pb push_back#define rsz resize#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()using pi = pair<int,int>;#define f first#define s second#define mp make_pairvoid setIO(string name = "") { // name is nonempty for USACO file I/O ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output if(sz(name)){ freopen((name+".in").c_str(), "r", stdin); // see Input & Output freopen((name+".out").c_str(), "w", stdout); }}
ll dp[1000001];
const int MOD = (int) 1e9 + 7;
int main(){ int n, x; cin >> n >> x; vi coins(n); for (int i = 0; i < n; i++) { cin >> coins[i]; } dp[0] = 1; for (int weight = 0; weight <= x; weight++) { for (int i = 1; i <= n; i++) { if(weight - coins[i - 1] >= 0) { dp[weight] += dp[weight - coins[i - 1]]; dp[weight] %= MOD; } } } cout << dp[x] << '\n';}