题解 | #数组分组#

// 这个题的重点在于，要定位到从nums里找到和为target的子集问题即可

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

// 从nums3选一部分找和为target,start为索引
void dfs(vector<int>& nums3,int target_sum,int& sum,bool& b,int start){
    // 如果找到了，直接return
    if(b)
        return;

    if(sum==target_sum){
        b=true;
        return;
    }

    for(int i=start;i<nums3.size();i++){
        // 尝试
        sum += nums3[i];
        dfs(nums3, target_sum, sum, b, i+1);
        // 回退
        sum -= nums3[i];
    }
}

int main() {
    int n;
    cin>>n;
    vector<int> nums(n);
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>nums[i];
        sum += nums[i];
    }

    // 如果不能分成两组，则直接返回
    if(sum%2!=0){
        cout<<"false";
        return 0;
    }    
    
    vector<int> nums1;  // 组1，倍数为3
    vector<int> nums2;  // 组2，倍数为5
    vector<int> nums3;  // 组3
    int sum_3=0;    // 组1的总和
    for(int i=0;i<nums.size();i++){
        if(nums[i]%3==0){
            nums1.push_back(nums[i]);
            sum_3 += nums[i];
        }
        else if (nums[i]%5==0)
            nums2.push_back(nums[i]);
        else
            nums3.push_back(nums[i]);
    }

    int target_sum=sum/2-sum_3; // 从第三组要找的目标和

    int tmp_sum =0;
    bool b=false;
    dfs(nums3,target_sum,tmp_sum,b,0);
    if(b)
        cout<<"true";
    else
        cout<<"false";

    return 0;
}
// 64 位输出请用 printf("%lld")