Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/description/

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:

Each of the array element will not exceed 100.

The array size will not exceed 200.

Thoughts

是否存在subset的和是sum / 2。 存在subset问题用01背包。action为选or not, dp[i][j]表示前i个数是否能凑成j。那么对于物品i, 当默认不做选择时，背包的价值应和i-1个时相同，即原来能凑成j现在也能，原来不能现在也不能f[i][j] = f[i-1][j]。 现在选了i的话能否凑成j, 选它能凑成j则代表目前背包里的值刚好凑成j-nums[i]，即dp[i-1][j-nums[i]] = true。

Code

/*
 * @lc app=leetcode id=416 lang=cpp
 *
 * [416] Partition Equal Subset Sum
 *
 * https://leetcode.com/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (41.44%)
 * Likes:    1472
 * Dislikes: 40
 * Total Accepted:    107.5K
 * Total Submissions: 258.2K
 * Testcase Example:  '[1,5,11,5]'
 *
 * 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:
 * 
 * 
 * Each of the array element will not exceed 100.
 * 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.
 * 
 * 
 * 
 * 
 */
class Solution {
public:
    bool canPartition(vector<int>& nums) {
         const int N = nums.size();
         int sum = 0;
         for (const auto num : nums) sum += num;
         if (sum & 1 == 1) return false;
         const auto V = sum / 2;
         vector<bool> dp(V + 1);
         dp[0] = true; 
         for (int i = 1; i <= N; ++i) {
             for (int j = V; j >= nums[i - 1]; --j) {
                 dp[j] = dp[j] || dp[j - nums[i - 1]];
             }
         }
         return dp[V];
    }
};

Analysis

Errors:

1. 初始化错误

时间复杂度O(n^2).

Ver.2

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) {
            return false;
        }

        int v = sum / 2;
        boolean[] f = new boolean[v + 1];
        f[0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = v; j >= nums[i]; j--) {
                f[j] = f[j] || f[j - nums[i]];
            }
        }

        return f[v];
    }
}