LeetCode 416 分割等和子集

題目連結

給定一個只包含正整數的非空陣列。是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等。

注意:

每個陣列中的元素不會超過 100
陣列的大小不會超過 200

範例 1:

輸入: [1, 5, 11, 5]

輸出: true

解釋: 陣列可以分割成 [1, 5, 5] 和 [11].

範例 2:

輸入: [1, 2, 3, 5]

輸出: false

解釋: 陣列不能分割成兩個元素和相等的子集.

典型的揹包問題~
首先和為奇數時肯定不能平均分，對和為偶數的情況就進行 $01$ 揹包，看最大值能否等於 $\frac{sum}{2}$ 即可，AC程式碼如下:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto i:nums) sum+=i;
        if(sum%2) return 0;
        int dp[sum+1],ans=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<nums.size();i++){
            for(int j=sum/2;j>=nums[i];j--){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
                ans=max(ans,dp[j]);
            }
        }
        return (ans==sum/2);
    }
};