题解 | 分割等和子集

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
#include <iostream>
#include <bitset>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  int x, sum = 0;//----------记录总和，如果总和为奇数，则必定不能均分
  bitset<50050> dp;//------------相当于50050位的二进制，也可以理解成bool型的数组，更省空间，这里dp【i】为true表示可以通过给出的值组合出i
  dp[0] = 1;//----------0肯定可以
  for (int i = 0; i < n; i++){
    cin >> x;
    sum += x;
    dp |= (dp << x);//--------------------维护dp
  }
  if (!(sum & 1) && dp[sum / 2]) cout << "true";
  else cout << "false";
}
// 64 位输出请用 printf("%lld")