416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

class Solution { public: bool canPartition(vector<int>& nums) { bool ans = false; int totalSum = 0; for (auto num : nums) { totalSum += num; } if (totalSum % 2 == 1) { return false; } int target = totalSum / 2; vector<bool> dp(target + 1, false); dp[0] = true; for (auto num : nums) { for (int i = target - num; i >= 0; i--) { if (dp[i]) { dp[i + num] = true; } } } return dp[target]; } };

=============

bool canPartition (vector < int > & nums) {
        bitset < 5001 > bits ( 1 );
         int sum = accumulate (nums.begin (), nums.end (), 0 );
         for ( int num: nums) bits | = bits << num;
         return (sum% 2 = = 0 ) && bits [sum >> 1 ];
    }