题解 | #数组分组#

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

bool canDevide(const vector<int> &rest,const int &index,const int &sum,const int &diff){
    if(index==rest.size()){
        return sum==diff;
    }

    if(canDevide(rest, index+1, sum+rest[index], diff))
        return true;
    
    return canDevide(rest,index+1,sum-rest[index],diff);
}

int main() {
    int n;
    cin>>n;
    vector<int> rest;
    int diff=0;
    for(int i=0;i<n;++i){
        int t;
        cin>>t;
        if(t%5==0){
            diff+=t;
        }
        else if(t%3==0){
            diff-=t;
        }
        else{
            rest.push_back(t);
        }
    }
    cout<<(canDevide(rest, 0, 0, diff)?"true":"false");
}
// 64 位输出请用 printf("%lld")

递归回溯

先求出3倍数和5倍数的差，剩下的数据每个都是加或减，回溯递归判断最终和是否会是差值