题意理解

把一个数组分成两部分（part1、part2），要求两部分的数字之和相等。其中，所有5的倍数（包括3和5的公倍数）要放在同一部分，其余3的倍数要放在同一部分。
让两部分之和相等，等价于从数组中找到一些数，使其和等于总和sum的一半。

方法一

深度优先搜索。 对于每一个数，有2种情况：放入part1；或者不放入part1（即放入part2），其中3的倍数必然放入part2。这样就构成了一个递归过程。每一个递归中遍历这2种情况，递归边界为遍历完所有的数字。

示意图如下:

具体代码如下：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool dp(vector<int> &num, int t,int k)
{
    if (t==0 && k==num.size()) return true;
    if (k==num.size()) return false;
    //如果只是3的倍数，不能加到该集合中。
    if (!(num[k]%3)) return(dp(num,t,k+1));
    if (num[k]==t) return true;
    //对于一个数有两种选择，加或者不加到该集合中
    return(dp(num,t-num[k],k+1)|dp(num,t,k+1));
}

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> num;
        int x,sum=0,part=0;//只要找到总和的一半即可，剩下的数字之和自然为总和的一半。
        for (int i=0;i<n;i++)
        {
            cin>>x;
            //如果是5的倍数，不放入数组num
            if (x%5)
                num.push_back(x);
            else
                part += x;
            sum += x;
        }
        //如果所有数之和不是偶数，则肯定是false
        if (sum%2)
        {
            cout<<"false"<<endl;
        }
        else
        {
            sum = sum/2;
            if (dp(num,sum-part,0))
                cout<<"true"<<endl;
            else cout<<"false"<<endl;
        }
        
        num.clear();
    }
}

时间复杂度： $O(2^N)O(2^N)$。每个数字都有两种情况，一共有$2^{N}2^N$种。
空间复杂度： $O(N)O(N)$。递归的深度为数组的长度。

方法二

动态规划。 要想知道是否有若干的数字之和为目标target，则遍历num数组中的每个数字num[i]：如果有某些数字之和为target-num[i]，那么必有某些数字之和为target。用dp[j]表示数字j是否是某些数字之和，则动态规划方程为：
$dp[j]=dp[j]\mathrm{\mid }\mathrm{\mid }dp[j-num[i]];dp[j]\; =\; dp[j]\; ||\; dp[j-num[i]];$
由于这里存在负数，所以对dp使用map类型，同时要注意j可能取值的范围。

具体代码如下：

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        vector<int> num;
        map<int,bool> dp;
        int x,sum=0,part=0,low=0;//只要找到总和的一半即可，剩下的数字之和自然为总和的一半。
        for (int i=0;i<n;i++)
        {
            cin>>x;
            //如果是3或者5的倍数，不放入数组num
            if (x%5 || x%3)
                num.push_back(x);
            if(!(x%5))
            {
                part += x;
            }
            //low是为了确定动态规划的范围。
            if (x<0) low += x;
            sum += x;
        }
        //如果所有数之和不是偶数，则肯定是false
        if (sum%2)
        {
            cout<<"false"<<endl;
        }
        
        else
        {
            //初始状态，边界
            for (int i=0;i<num.size();i++)
            {
                dp[num[i]] = true;
            }
            //动态规划过程
            for (int i=0;i<num.size();i++)
            {
                for (int j=sum/2-part;j>=low;j--)
                {
                    dp[j] = dp[j] || dp[j-num[i]];
                }
            }
            if(dp[sum/2-part]) cout<<"true"<<endl;
            else cout<<"false"<<endl;
        }
        num.clear();
    }
}

时间复杂度： $O(NM)O(NM)$。其中M为所有数字之和。
空间复杂度： $O(N)O(N)$。开辟了一个map类型记录某个数字是否为某些数字之和。