题解 | 数组分组 使用set动态规划

#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, sum = 0, sum3 = 0, sum5 = 0, sume = 0, sum_aim = 0, t;
    vector<int> ve;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        sum += t;
        if (t % 5 == 0) {
            sum5 += t;
        } else {
            if (t % 3 == 0) {
                sum3 += t;
            } else if (t != 0)
                ve.emplace_back(t);
        }
    }
    sume = sum - sum3 - sum5;
    if (sum % 2 != 0) {
        cout << "false";
        return 0;
    }
    sum_aim = sum / 2 - min(sum3, sum5);

    if (ve.empty()) {
        if (sum3 == sum5)
            cout << "true";
        else
            cout << "false";
        return 0;
    }
    sort(ve.begin(), ve.end());
    unordered_set<int> dp, dp_last;
    dp.insert(0);
    dp_last = dp;
    for (int i = 0; i < ve.size(); ++i) {
        for (auto& val : dp_last) {
            dp.insert(val + ve[i]);
            if (dp.find(sum_aim) != dp.end()) {
                cout << "true";
                return 0;
            }
        }
        dp_last = dp;
    }

    cout << "false";
    return 0;
}