题目的主要信息：

• 对输入的n个数，询问能否被分成两组，且两组的和相等
• 其中第一组必须包含所有5的倍数，第二组必须包含3的倍数（不含5的倍数）
• 其他数字任意放
• 可以分出空数组，因为正负数和可能为0

方法一：集合枚举

具体做法：

在输入的时候直接开始计算5的倍数的和与3的倍数的和，然后剩余的数字再加入数组，同时计算总和。

然后我们用unordered_set开始枚举剩余的数能够组成的全部和，因此可以有空数组，因此先加0加入集合，然后遍历剩余的数组，对于每一个元素，都有与当前集合每一个元素相加，然后加入集合，因此在加之前，用另一个集合记录当前集合，避免加入新元素后受影响。

最后遍历所有的枚举，检查是否能找出一个和，能满足题目要求，即与第一组的和相加后等于第二组的和与剩余和减去这个和相加。

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

int main(){
    int n;
    while(cin >> n){
        vector<int> arr;
        int sum3 = 0;
        int sum5 = 0;
        int rest = 0;
        for(int i = 0; i < n; i++){ 
            int x;
            cin >> x;
            if(x % 5 == 0) //先求一个组的和
                sum5 += x;
            else if(x % 3 == 0) //再求另一个组的和
                sum3 += x;
            else{
                arr.push_back(x); //剩余的加入数组并求和
                rest += x;
            }
        }
        unordered_set<int> s1, s2;
        s1.insert(0); //枚举所有组合的不重复和，0为空数组
        for(int i = 0; i < arr.size(); i++){ //遍历每一个数字
            s2 = s1; //每个数字都要与当前集合的每个数相加组成新的和
            for(auto it: s2)
                s1.insert(it + arr[i]);
        }
        bool flag = false;
        for(auto it: s1){ //遍历枚举的集合
            if(it + sum5 == sum3 + rest - it){ //分成两部分后相等
                flag = true;
                break;
            }
        }
        cout << (flag ? "true" : "false") << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n!)O(n!)$，枚举所有的组合是一个全排列，最坏$nn$个数没有5或者3的倍数，全部都要枚举组合
• 空间复杂度：$O(n!)O(n!)$，集合最大需要记录所有的组合和

方法二：递归

具体做法：

与方法一类似，我们将5的倍数的数累加（记为第一组），3的倍数的数累加（记为第二组），剩余的数加入数组中。然后我们可以递归处理剩余的数。

对于剩余的数，每次我们可以选择将其加入第一组或者是第二组，加入第一组我们可以记为加，加入第二组我们可以记为减，直到递归到最后我们对数组剩余中这些数的累加减和等于最初5的倍数和3的倍数的和他们的差的绝对值，说明剩余的数是可以填补这个空缺的。

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

bool judge(int i, vector<int>& arr, int sum1, int sum2){ //剩余的数组中组合出等于3和5和之差的
    if(i == arr.size())
        return abs(sum1) == sum2;
    else //加放一边，减放另一边
        return judge(i + 1, arr, sum1 + arr[i], sum2) || judge(i + 1, arr, sum1 - arr[i], sum2);
}

int main(){
    int n;
    while(cin >> n){
        vector<int> arr;
        int sum3 = 0;
        int sum5 = 0;
        int rest = 0;
        for(int i = 0; i < n; i++){ 
            int x;
            cin >> x;
            if(x % 5 == 0) //先求一个组的和
                sum5 += x;
            else if(x % 3 == 0) //再求另一个组的和
                sum3 += x;
            else{
                arr.push_back(x); //剩余的加入数组并求和
            }
        }
        if(judge(0, arr, 0, abs(sum5 - sum3)))
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，其中$nn$为输入的数，最坏情况下全部到了剩余数组，递归的公式为$T(n)=2T(n-1)T(n)=2T(n-1)$，这是一个树型递归
• 空间复杂度：$O(n)O(n)$，递归栈深度最大为$nn$