416. Partition Equal Subset Sum ------M

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 total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 == 1)
            return false;
        const int target = total / 2;
        unordered_set<int> S;
        for (auto num : nums) {
            unordered_set<int> newS;
            for (const auto& val : S) {
                if (val + num == target) {
                    return true;
                }
                if (val + num < target) // coz num[i] >= 1
                    newS.insert(val + num);
            }
            if (num == target)
                return true;
            S.insert(num);
            S.insert(newS.begin(), newS.end());
        }
        return false;
    }
};

Mistakes:

加入v的时候，忘记了要检查是否为target

-------------------------用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;
    }
};

learned：

       bool dp[s + 1];
       memset(dp, false, sizeof(dp));

可以改为： vector<bool> dp(s+1, false) 但是最终结果，速度上会慢很多。 一个是95%， 一个是55%