题解 | #数组分组#

输入的所有数的集合:nums

根据题意，尝试把nums分成两组g5和g3

s5为能被5整除的数字的集和，s3为能被3整除（不能被5整除）的数字的集合

left为nums中排除s5和s3数字的所有剩余数字

l5是left中，和s5一起分到g5的数字；类似的，l3是left中，和s3一起分到g3的数字.

根据上述定义，有：

nums = g5 + g3

g5 = s5 + l5, g3 = s3 + l3

当sum(g5)=sum(g3)时满足均等分组的可能

当sum(l5)=sum(nums)/2-sum(s5)时满足均等分组，所以我们尝试找满足左式的情况。

定义target := sum(nums)/2-sum(s5)，target是一已知固定值。

不失一般性，假设初始时所有left中元素都在l5中，假如此时sum(l5)=target则返回true；否则，尝试将现有l5中一部分数字拿出来（因为sum(nums)一定，会自动放入l3中）看剩下的数字是不是等于target。

我们遍历g5来考虑拿出当前数字后，产生的sum(g5)会不会等于target，如果等于则返回true。 我们交替地使用两个set对象，s1保存考虑当前数字前，通过移除（或保留）g5元素所能够得到的sum(g5');s2保存根据s1移除（或保留）当前数字后能得到的sum(g5')。

在完成g5的遍历后，移除（或保留）任意g5中数字所产生的sum(g5')都被考虑到了，检查target是否存在即可确定能否均分原数组。

因为每遍历到一个新的数字，s1到s2处理的元素个数都翻倍了，所以时间复杂度为O(2^N)，空间复杂度为O(2^N)

#include<vector>
#include<set>

using namespace std;

int main(){
    int n, sum=0, sum5=0, cur, count5=0, sum5g=0;
    vector<int> g5;
    cin >> n;
    g5.resize(n);
    while(n--){
        cin >> cur;
        if(!(cur%5))
            sum5+=cur;
        else if(cur%3){
            g5[count5++] = cur;
            sum5g+=cur;
        }
        sum+=cur;
    }
    if(sum%2){
        cout << "false";
    }
    else{
        g5.resize(count5);
        int target = (sum>>1)-sum5;
        if(sum5g == target){
            cout << "true";
            return 0;
        }
        set<int> *s1, *s2;
        s1 = new set<int>{sum5g};
        s2 = new set<int>;
        for(int i=0;i<g5.size();++i){
            *s2 = *s1;
            for(auto c:*s1)
                s2->insert(c-g5[i]);
            if(s2->find(target)!=s2->end()){
                cout << "true";
                delete s1;
                delete s2;
                return 0;
            }
            *s1 = *s2;
        }
        delete s1;
        delete s2;
        cout << "false";
    }
    return 0;
}