416. Partition Equal Subset Sum

2D array

/*
 * @lc app=leetcode id=416 lang=cpp
 *
 * [416] Partition Equal Subset Sum
 *
 * https://leetcode.com/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (46.89%)
 * Likes:    12640
 * Dislikes: 260
 * Total Accepted:    1M
 * Total Submissions: 2.1M
 * Testcase Example:  '[1,5,11,5]'
 *
 * Given an integer array nums, return true if you can partition the array into
 * two subsets such that the sum of the elements in both subsets is equal or
 * false otherwise.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [1,5,11,5]
 * Output: true
 * Explanation: The array can be partitioned as [1, 5, 5] and [11].
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [1,2,3,5]
 * Output: false
 * Explanation: The array cannot be partitioned into equal sum subsets.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 *
 *
 */

// @lc code=start
class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size();
        int subset_sum = sum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(subset_sum + 1));
        dp[0][0] = true;

        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1];
            for(int j = 0; j <= subset_sum; j++) {
                if(j < cur) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] || (dp[i - 1][j - cur]);
            }
        }
        return dp[n][subset_sum];
    }
};
// @lc code=end

• T: $O(M \cdot N)$：N 是 array 長度，M 代表 subset sum 的大小。
• S: $O(M \cdot N)$，M 代表 subset sum 的大小。

DP improved

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int target = sum >> 1;
        vector<bool> dp(target + 1);
        dp[0] = true;

        for (int num : nums)
        {
            for (int i = target; i >= num; --i)
            {
                dp[i] = dp[i] || dp[i - num];
                if (dp[target])
                {
                    return dp[target];
                }
            }
        }
        return dp[target];
    }
};

• T: $O(M \cdot N)$：N 是 array 長度，M 代表 subset sum 的大小。
• S: $O(M)$，M 代表 subset sum 的大小。