题解 | 数组分组

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool dfs(vector<int>& nums, int idx, int target) {
    if (target == 0) return true;
    if (idx >= nums.size()) return false;

    // 尝试选或不选当前数字
    return dfs(nums, idx + 1, target - nums[idx]) || dfs(nums, idx + 1, target);
}

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

    vector<int> arr(n);
    vector<int> others;

    int sumA = 0, sumB = 0, othersSum = 0;

    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        if (arr[i] % 5 == 0) {
            sumA += arr[i];
        } else if (arr[i] % 3 == 0) {
            sumB += arr[i];
        } else {
            others.push_back(arr[i]);
            othersSum += arr[i];
        }
    }

    int diff = sumB - sumA + othersSum;

    // 检查是否可被2整除，否则无法平分
    if (diff % 2 != 0) {
        cout << "false" << endl;
    } else {
        int target = diff / 2;
        // 在others中寻找一个子集和为 target
        if (dfs(others, 0, target)) {
            cout << "true" << endl;
        } else {
            cout << "false" << endl;
        }
    }

    return 0;
}