416.canPartition.cpp

//
// Created by zhaohongyan on 2020/10/11.
//

#include <bits/stdc++.h>
using namespace  std;
bool res = false;

bool canPartition(vector<int>& nums) {
    int n = nums.size();
   if(n < 2){
       return false;
   }
   int sum = accumulate(nums.begin(),nums.end(),0);
   if(sum % 2 != 0 ){
       return false;
   }
   int maxelem = *max_element(nums.begin(),nums.end());
   if(maxelem > sum / 2){
       return false;
   }
   int target = sum / 2;
   vector<vector<int>> dp(n,vector<int>(target+1, 0));
    for (int i = 0; i < n; ++i) {
        dp[i][0] = true;
    }
    dp[0][nums[0]] = true;
    for (int j = 1; j < n; ++j) {
        for (int i = 1; i < target + 1; ++i) {
            if(i > nums[j]){
                dp[j][i] = dp[j - 1][i] | dp[j - 1][i - nums[j]];
            }
            else{
                dp[j][i] = dp[j-1][i];
            }
        }

    }
    return dp[n-1][target];

}

int main(){
    vector<int> nums{100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,99,97};
//     vector<int> nums{1, 5, 10, 5};
//    cout << nums.size();

    cout << canPartition(nums);
    return 0;
}