题解 | 分割等和子集

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

int main() {
    int n;
    cin>>n;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int total_sum=accumulate(arr.begin(), arr.end(), 0);
    if(total_sum%2==1){
        cout<<"false";
        return 0;
    }
    int target=total_sum/2;
    vector<vector<bool>> dp(n+1,vector<bool>(target+1,false));//dp[i][j]表示前i个数能否构成数组为j的数
    for(int i=0;i<=n;i++){
        dp[i][0]=true;
    }
    for(int i=1;i<=n;i++){//i表示前i个数据
        for(int j=1;j<target+1;j++){
            if(j>=arr[i-1]){
                dp[i][j]=dp[i-1][j]||dp[i-1][j-arr[i-1]];
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<(dp[n][target]==true?"true":"false");
    return 0;
}
// 64 位输出请用 printf("%lld")