416. Partition Equal Subset Sum

解題思路

1. 如果 array 的總和是奇數，那麼不用想了，一定找不到能分兩半的組合

2. 接下來，題目被簡化成找 target = sum / 2 在 array 中是否有該組合

原本想用 set 做，traverse array[i] 的時候把新的可能加進去，但沒想到效率很慢。

改用 bool vector 來記錄 sum = i 的組合是否能找到。

程式碼

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
            sum += nums[i];
        
        if(sum % 2 == 1) return false;

        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for(int i=0; i<nums.size(); i++)
        {
            for(int j=target; j>=nums[i]; j--)
                dp[j] = dp[j] || dp[j - nums[i]];
        }
        return dp[target];
    }
};