SHARE
TWEET

Untitled

a guest Mar 20th, 2017 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         auto sum=accumulate(nums.begin(),nums.end(),0);
  5.         if(sum%2!=0)
  6.             return false;
  7.        
  8.         sum/=2;
  9.         auto n=nums.size();
  10.         vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
  11.         for(int i=0;i<=n;++i)
  12.         {
  13.             dp[i][0]=true;
  14.         }
  15.        
  16.         for(int i=1;i<sum+1;++i)
  17.         {
  18.             dp[0][i]=false;
  19.         }
  20.        
  21.         for(int i=1;i<=n;++i)
  22.             for(int j=1;j<=sum;++j)
  23.             {
  24.                 if((j-nums[i-1])>=0)
  25.                     dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
  26.                 else
  27.                     dp[i][j]=dp[i-1][j];
  28.             }
  29.        
  30.         return dp[n][sum];
  31.     }
  32. };
RAW Paste Data
Top