Problem description:

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:
Each of the array element will not exceed 100.
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.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.empty()) return false;
        
        sort(nums.begin(), nums.end());
        int sum= 0;
        for(auto n: nums)
            sum+= n;
        
        if(sum %2 != 0) return false; //can not be partitioned into two subset
        int target= sum /2;
        vector<bool> dp(target+1, 0);
        dp[0]= true;
        for(auto n: nums){
            for(int i= target; i>= n; i--){
                dp[i]= dp[i] || dp[i-n];
            }
        }
        
        return dp[target];
        
    }
};