vivek_ragi

partition_SUM

Jun 30th, 2021
794
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& arr) {
  4.         int n = arr.size();
  5.         int sum = 0;
  6.         for(auto x: arr) {
  7.             sum += x;
  8.         }
  9.        
  10.         if(sum % 2) {
  11.             return false;
  12.         }
  13.         sum/=2;
  14.        
  15.         int dp[n + 1][sum + 1];
  16.        
  17.         for(int j = 0; j <= sum; ++j) {
  18.             dp[0][j] = 0;
  19.         }
  20.        
  21.         for(int j = 0; j <= n; ++j) {
  22.             dp[j][0] = 1;
  23.         }
  24.        
  25.         for(int i = 1; i <= n; ++i) {
  26.                 int cur = arr[i - 1];
  27.             for(int j = 1; j <= sum; ++j) {
  28.                
  29.                 if(cur > j) {
  30.                     dp[i][j] = dp[i - 1][j];
  31.                 }
  32.                 else {
  33.                     dp[i][j] = dp[i - 1][j] or dp[i - 1][j - cur];
  34.                 }
  35.             }
  36.            
  37.         }
  38.        
  39.        
  40.         return dp[n][sum];
  41.     }
  42. };
RAW Paste Data