题解 | #数组分组#

动态规划，想办法转化力扣的416题，分割相等其实就是找一个集合使它们中有数的组合可以加起来等于某个数，而这个数在416题是和的一半，我这里就是x/2

#include <algorithm>
#include <vector>

using namespace std;

bool judge(int sum5,int sum3,int nor35,vector<int>&v){
    
    int diff = abs(sum5-sum3);
    if(nor35==0&&(diff==0)) return true;//这里的逻辑好理解差值为0，且没有第三组
    int x = nor35+diff;//这里求和想看看它们能否被评分因为整个集合都是整数，如果是
    //奇数除以2是小数，不可能又和可以组成，只有能平分成整数在考虑有没有数可以组合。
    if(diff==0&&(v.size()==0))return true;
    
    if(x%2!=0) return false;
    else{
        x/=2;
        vector<vector<int>> dp(v.size(),vector<int>(x+1,0));
        for(int i =0;i<v.size();i++){
            dp[i][0]=1;
        }
       
            dp[0][v[0]]=1;
        
        
        for(int i = 1;i<v.size();i++){
            for(int j =1;j<x+1;j++){
                if(j>=v[i])dp[i][j]=dp[i-1][j-v[i]]||dp[i-1][j];//这里i-1代表
                //没有v[i]的时候的和也可以组成j
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[v.size()-1][x];
       
    }
     
    
}

int main() {
    int n;
    while(cin>>n){
        vector<int> v;
        int sum5=0,sum3=0,sum=0,nor35=0;
        int temp;
        for(int i =0;i<n;i++){
            cin>>temp;
            if(temp%5==0){
                sum5+=temp;
            }
            else if(temp%3==0){
                sum3+=temp;
            }
            else{
                nor35+=abs(temp);//加绝对值对最后判断能不能分成两个和相等时没有
                //影响，不信你自己试试看
                v.push_back(abs(temp));
            }
            
        }
        bool canpatiton = false;
            canpatiton = judge(sum5,sum3,nor35,v);
            cout<<boolalpha<<canpatiton<<endl;
        
    }
}