题解 | #数组分组#

其实直觉来看应该是很标准的DFS，每个数字只有两种可能，放在A数组和放在B数组，重要的是要记得恢复原本数组状态。

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

int suma = 0; //记录数组A的和
int sumb = 0; //记录数组B的和
int cnt = 0;
int c[55];


bool dfs(int i){
    // cout << i << " " << suma << " " << sumb << endl;
    if (i == cnt){
        if (suma == sumb) return true;
        return false;
    }
    // i 放在A中
    suma += c[i];
    if (dfs(i+1)) return true;
    suma -= c[i];

    // i 放在B中
    sumb += c[i];
    if (dfs(i+1)) return true;
    sumb -= c[i];
    return false;
}


int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int a; cin >> a;
        if (a % 5 == 0) suma += a;
        else if (a % 3 == 0) sumb += a;
        else{
            c[cnt++] = a;
        }
    }
    if (dfs(0)) cout << "true";
    else cout << "false";
    return 0;
}
// 64 位输出请用 printf("%lld")