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.

A:

-----------------首先考虑用Set , 记录所有比其更小的 half sum -------------------

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
        if(totalSum %2 )
            return false;
        int target = totalSum>>1;
        unordered_set<int> S;
        for(auto v : nums)
        {
            unordered_set<int> newS;
            for(auto k : S)
            {
                if(k+v<target)
                    newS.insert(k+v);
                else if(k+v == target)
                    return true;
            }
            if(v==target)
                return true;            
            S.insert(v);
            S.insert(newS.begin(),newS.end());            
        }
        return false;
    }
};

-------------------------用Set 可以pass，然而大多数submission比我们好-----------------
可以  利用每个数都小于100， 不超过200个数。 这样不用Set--------

class Solution {
public:
    bool f(vector<int>& nums, int s) {
       bool dp[s + 1];
       memset(dp, false, sizeof(dp));
       dp[0] = true; 
       for(int n : nums) {
           for(int i=s;i>=n;i--) {
               dp[i] = dp[i] || dp[i - n];
           }
       }        
       return dp[s];
    }
    
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int n : nums) sum += n;
        
        return (sum%2 == 0) ? f(nums, sum/2) : false;
    }
};