题解 | #分割等和子集#

如果能分成相等的两份的话，那么sum一定是偶数

1.sum是奇数的话 就false

2.如果是偶数 就变成了0-1背包问题 求数组和是否有和为sum / 2的子数组 有就是true

3.没有就false

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

// 数组元素加和 100 * 500 = 50000 sum / 2是25000 所以要开大于25000
const int N = 25000;
int f[N], a[N], sum;

int main() {
    int n;
    cin >> n;

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        sum += a[i];
    }

    if(sum % 2 != 0) cout << "false" << endl;
    else{
        f[0] = 1;
        for(int i = 1; i <= n; i ++)
            for(int j = sum / 2; j >= a[i]; j --){
                f[j] = f[j] || f[j - a[i]];
            }
        if(f[sum / 2]) cout << "true" << endl;
        else cout << "false"<< endl;
    }

}