题解 | #数组分组#(数组+回溯)

解题思路

1.f0,f3,f5分别表示元素总和,3倍数元素和,5倍数元素和,当f0为奇数时直接输出false;在非3及5倍数数组中寻找是否有元素集合和为target = f0 / 2 - f3;使用回溯的思路校验是否有元素集合和为target;

代码

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

bool dfs(vector<int>& v, int i, int target){ //v的集合中是否有元素和为target
    if(i == v.size()) return target == 0;
    return dfs(v, i + 1, target - v[i]) || dfs(v, i + 1, target); //分两种情况讨论,是否选中v[i]
}

int main(){
    int n;
    cin >> n;
    vector<int> v; //存储既不是3的倍数,又不是5的倍数的元素
    int f0 = 0, f3 = 0, f5 = 0;
    for(int i = 0; i < n; i++){
        int val;
        cin >> val;
        f0 += val;
        if(abs(val) % 5 == 0){
            f5 += val;
        }
        else if(abs(val) % 3 == 0){
            f3 += val;
        }
        else{
            v.push_back(val);
        }
    }
    int target = f0 / 2 - f3; //在数组v中寻找是否有元素集合为target
    if(abs(f0) % 2 == 1 || !dfs(v, 0, target)){
        cout << "false";
    }
    else{
        cout << "true";
    }
    return 0;
}