题解 | #分割等和子集# 是否有解，只需要一维dp

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

int main() {
    int n,t,sum=0;
    cin>>n;
    vector<int> nums;nums.reserve(n);
    //由于背包容量要最后才知道，这道题没有办不保存原数组
    while(n-- &&cin>>t){
        nums.push_back(t);
        sum+=t;
    }
    if(sum%2){
        cout<<"false"<<endl;//奇数，无解
        return 0;
    }
    sum/=2;
    vector<bool> dp(sum+1,false);
    int i,j,boundary,curMax=0;
    dp[0]=true;
    //只是判断是否有解，不需要用二维数组来dp

    for(i=0;i<nums.size();++i){
        boundary=min(sum-nums[i],curMax);
        for(j=boundary;j>=0;--j){
            
            if(dp[j]){
                dp[j+nums[i]]=true;
                curMax=max(j+nums[i],curMax);
                if(j+nums[i]==sum)break;
            }
        }
        
    }

    cout<<(dp[sum]?"true":"false")<<endl;

}
// 64 位输出请用 printf("%lld")