题解 | #分割等和子集#

解题思路：

• 输入时记录数组和$sumsum$， 如果$sum\mathrm{\%}2\mathrm{\ne }0sum\; \backslash \%\; 2\; \backslash neq\; 0$直接输出false
• 否则令$d{p}_j\mathrm{（}01\mathrm{背}\mathrm{包}\mathrm{）},(0\le j\le sum\mathrm{/}2)dp\_j（01背包）,(0\; \backslash leq\; j\; \backslash leq\; sum/2)$，表示处理第$ii$个数时，容量为$jj$的背包，问题变为使用i和上一轮的值是否能构成$jj$。 状态转移方程：

• 最后根据$d{p}_{sum\mathrm{/}2}dp\_\{sum/2\}$的值是否为1输出true或false

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    vector<int> v(n+1);
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        cin>>v[i];
        sum += v[i];
    }
    int flag = 1;
    if(sum % 2 != 0) flag = 0;
    else {
        vector<int> dp(sum/2+1);
        for(int i = 1; i <= n; ++i){
            for(int j = sum/2; j >= v[i]; --j){
                if(j == v[i] || dp[j-v[i]] != 0) dp[j] = 1;
                else dp[j] = 0;
            }

        }
        flag = dp[sum/2];
    }
    cout<<(flag? "true": "false")<<endl;


    return 0;
}