题解 | #数组分组#

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

vector<int> b5;
vector<int> b3;

bool dfs(vector<int> num,int start){
    if(start==num.size()){//递归终止条件
        int s5=0;int s3=0;
        for(int x:b5)
            s5+=x;
        for(int x:b3)
            s3+=x;
        if(s5==s3)
            return true;
        else
            return false;
    }
        b5.push_back(num[start]);//加入数组1
        if(dfs(num,start+1))
            return true;
        b5.pop_back();
        b3.push_back(num[start]);//加入数组2
        if(dfs(num,start+1))
            return true;
        b3.pop_back();
    
    return false;//都不行，则返回false
}

int main() {
    int n;
    cin >> n;
    vector<int> num;
    for(int i=0;i<n;++i){
        int x;
        cin >>x;
        if(x%5==0)//遇到5或3倍数直接添加进对应数组
            b5.push_back(x);
        else if(x%3==0)
            b3.push_back(x);
        else
            num.push_back(x);
    }
    if(dfs(num,0))
        cout << "true"<<endl;
    else
        cout << "false"<<endl;
    /*for(int i=0;i<b5.size();++i)
        cout << b5[i] << ' ';
    cout << endl;
    for(int i=0;i<b3.size();++i)
        cout << b3[i] << ' ';*/
}
// 64 位输出请用 printf("%lld")