Code

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

const int inf = 1e7;
const int max_m = 3000 + 1;

void solve(vector<int> &a, int m) {
    int n = a.size();

    // dp[i][sum][cost] is the minimum number of operations needed to make the
    // sum of the remaining elements equal to sum, when we are only dealing with
    // elements [0...i] and the cost of leaving the i-th element is cost.

    // Note that taking an element in the final array is always free.
    // Leaving an element for the first time costs 1.
    //
    // Answer: dp[n - 1][m][1]
    vector<vector<vector<int>>> dp(
        n + 1, vector<vector<int>>(max_m + 1, vector<int>(2, inf)));

    a.insert(a.begin(), 0);
    dp[0][0][0] = 0;
    dp[0][0][1] = 0;

    for (int i = 1; i <= n; i++) {
        for (int sum = 0; sum <= max_m; sum++) {
            for (int cost = 0; cost <= 1; cost++) {
                // Taking an element is always free.
                int take_it = sum >= a[i] ? dp[i - 1][sum - a[i]][1] : inf;

                // Leaving an element would you cost you the price of that
                // element.
                int leave_it = cost + dp[i - 1][sum][0];

                dp[i][sum][cost] = min(take_it, leave_it);
            }
        }
    }

    for (int sum = 1; sum <= m; sum++) {
        if (dp[n][sum][1] >= inf) {
            cout << -1 << endl;
        } else {
            cout << dp[n][sum][1] << endl;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    solve(a, m);
    return 0;
}