题解 | #数组分组#

#include <bits/stdc++.h>

using namespace std;

bool dp(vector<int> &nums, int t, int k){
    if(t == 0 && k == nums.size()) return true;
    if(k == nums.size()) return false;
    
    //如果只是3的倍数，不能加到该集合中。
    if(nums[k] % 3 == 0) return dp(nums, t, k + 1);
    if(nums[k] == t) return true;
    
    //对于一个数有两种选择，加或者不加到该集合中
    return dp(nums, t - nums[k], k + 1) || dp(nums, t, k + 1); //
}

int main(){
    int n = 0;
    while(cin >> n){
        /*//法一
        vector<int> nums;
        int sum = 0; //只要找到总和的一半即可，剩下的数字之和自然为总和的一半。
        int part = 0; //5的倍数的数字之和
        for(int i =0; i < n; i++){
            int num = 0;
            cin >> num;
            if(num % 5 == 0) part += num; //如果是5的倍数，不放入数组nums
            else nums.push_back(num);
            
            sum += num;
        }
        
        //如果所有数之和不是偶数，则肯定是false
        if (sum%2){
            cout<<"false"<<endl;
        }
        else{
            sum = sum / 2;
            if(dp(nums, sum - part, 0)){
                cout << "true" << endl;
            }
            else cout<<"false"<<endl;
        }
        
        nums.clear();*/
        
        //法二
        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); //剩余的加入数组并求和
                rest += x;
            }
        }
        
        //
        unordered_set<int> s1, s2;
        s1.insert(0); //枚举所有组合的不重复和，0代表空数组
        for(int i = 0; i < arr.size(); i++){ //遍历剩余的每一个数字,枚举所有可能性
            s2 = s1; //
            for(auto iter : s2){
                s1.insert(iter + arr[i]); //s1中保存的是所有的剩余数的和的可能性
            }
        }
        
        bool res = false;
        for(auto iter : s1){ //遍历枚举的集合
            if(iter + sum5 == sum3 + (rest - iter)){ //分成两部分后相等
                res = true;
                break;
            }
        }
        
        cout << (res ? "true" : "false") << endl;
    }
    
    return 0;
}