MEDIUM

416. Partition Equal Subset Sum

Given a non-empty array nums 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.

Example

Input:

nums = [1,5,11,5]

Output:

true

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

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums[i] ≤ 100

Solution: Dynamic Programming (Subset Sum)

Time Complexity: O(n * sum), where n is the number of elements and sum is the target subset sum.
Space Complexity: O(sum), for the DP array.

C++

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;
        int target = total / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};