题解 | #数组分组#

****************************************

注意这两题的区别

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool judge(int i, vector<int>& arr, int sum1, int sum2);
int main() {
    /*
        我们将5的倍数的数累加（记为第一组），3的倍数的数累加（记为第二组），剩余的数加入数组中。然后我们可以递归处理剩余的数。
        对于剩余的数，每次我们可以选择将其加入第一组或者是第二组，加入第一组我们可以记为加，加入第二组我们可以记为减，直到递归到最后我们对数组剩余中这些数的累加减和等于最初5的倍数和3的倍数的和他们的差的绝对值，说明剩余的数是可以填补这个空缺的。

    */

    int n;
    while (cin >> n) {
        vector<int>arr;
        int sum3 = 0;
        int sum5 = 0;
        int rest = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x % 5 == 0) sum5 += x;
            else if (x % 3 == 0) sum3 += x;
            else arr.push_back(x);
        }
        if (judge(0, arr, 0, abs(sum5 - sum3)))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
}
bool judge(int i, vector<int>& arr, int sum1, int sum2) {
    if (i == arr.size())
        return abs(sum1) == sum2;
    else //加放一边，减放另一边，i+1是下一轮操作的下标
        //这样就处理了dp难处理负数的情况
        //把一个正数放在sum3和把他的相反数放进sum5对于最后求差的帮助是一样的
        return judge(i + 1, arr, sum1 + arr[i], sum2) ||
               judge(i + 1, arr, sum1 - arr[i], sum2);
}
// 64 位输出请用 printf("%lld")