题解 | 数组分组

写完代码才发现能优化的地方太多了 果然还是太嫩了，优化点如下：

首先可以直接用n % 3 == 0来判断n是3的倍数 不用先除再乘like a idiot

其次就是要体会 if(index == c.size()) {return target == 0;}和if(index ==c.size()&&target ==0) {return true;}的区别 前者是只要index等于c.size()就一定会终止返回了，后者则是必须要target才返回 小细节酿造大差错

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

bool find(vector<int>& c, int target, int index) {
    if(index == c.size()) {
        return target == 0;
    }

    if(find(c, target + c[index], index + 1)) return true;

    if(find(c, target - c[index], index + 1)) return true;


    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> a; //5的倍数 可能也是3的倍数
    vector<int> b; //3的倍数 但不是5的倍数
    vector<int> c; //不是3也不是5的倍数
    for(int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        int divisor_3 = k / 3;
        int divisor_5 = k / 5;
        if(divisor_5 * 5 == k) a.push_back(k);
        else if(divisor_3 * 3 == k) b.push_back(k);
        else c.push_back(k);
    }

    int sum_a = 0, sum_b = 0;
    for(const int& n: a) sum_a += n;
    for(const int& n: b) sum_b += n;

    int target = abs(sum_a - sum_b);

    //用target去加c[i]或者(-c[i])，最后结果为0的话就表明存在方案
    cout << (find(c, target, 0) ? "true" : "false") << endl;
    return 0;
}