题解 | #数组分组#

#include <bits/stdc++.h>
using namespace std;

bool dfs(vector<int>& sel, int target, int k){
    if(k>=sel.size()&&target!=0) return false;
    if(k>=sel.size()&&target==0) return true;
    return dfs(sel, target-sel[k], k+1)||dfs(sel, target, k+1);
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> arr(n);
        vector<int> sel;
        int left = 0, total = 0;
        for(int i=0;i<n;i++){
            cin>>arr[i];
            if(arr[i]%5==0) left+=arr[i];
            total+=arr[i];
            if(arr[i]%5!=0&&arr[i]%3!=0) sel.push_back(arr[i]);
        }
        if(total&1){
            cout<<"false";
            break;
        }
        int target = total/2-left;
        bool ret = dfs(sel, target, 0);
        cout<<(ret?"true":"false");
    }
}

转换问题，最后也不要用DP写了，DFS两下就写完了