LeetCode416

EX416

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.

Example1:

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
           

Example2:

Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
           

Solution:

這是一個典型的背包問題，我們需要做的，就是當背包的容量剛好為nums中所有物品重量之和的一半時，是否可以剛好填滿就行。
  子問題為：對于物體i(i < nums.size())，當背包容量為j時(j <= sum/2)，是否存在能夠剛好裝滿背包且包含物品i的組合。
  dp[j] = dp[j] || dp[j-nums[i]];
  nums[i]為物品i的重量
           

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size(), sum = , half = ;
        for(int i = ; i < len; i++) {
            sum += nums[i];
        }
        //如果sum為奇數，return false
        if (sum & )
            return false;
        half = sum/;
        vector<int> dp(half+, );
        dp[] = ;
        for (int i = ; i < len; i++) {
            //單副本，未避免已經使用的物品對不同j産生影響，是以top to down
            for (int j = half; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[half];
    }
};