Time Cost

16min01s

Implementation

dp[i] represents if sum=i is possible. We also got some pre-condition which could filter some false result. (1) If the total sum of every elements in nums vector is odd, then is false; (2) If the largest element in vector is larger than the half of total, then is false.

Code

• My Solution

  class Solution {
  public:
    bool canPartition(vector<int>& nums) {
        if (nums.size() == 1) return false;
        int mx = 0;
        int total = 0;
        for (int num: nums) {
            total += num;
            mx = max(mx, num);
        }
  
        if (total & 1) return false;
        if (mx > (total/2)) return false;
  
        // before index i, we can have these values
        int target = total / 2;
        vector<char> dp(target+1, 0);
        dp[0] = 1;
        for (int num: nums) {
            for (int i = target; i>=num; i--) {
                dp[i] = dp[i] || dp[i-num];
            }
            if (dp[target]) return true;
        }
  
        return dp[target];
    }
  };