Given a non-empty array nums 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.

    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

    https://labuladong.gitbook.io/algo/mu-lu-ye/bei-bao-zi-ji


    Runtime: 988 ms, faster than 9.15% of JavaScript online submissions for Partition Equal Subset Sum.
    Memory Usage: 68.8 MB, less than 44.54% of JavaScript online submissions for Partition Equal Subset Sum.

    1. /**
    2.  * @param {number[]} nums
    3.  * @return {boolean}
    4.  */
    5. var canPartition = function(nums) {
    6.     const sum = nums.reduce((prev, current) => prev + current, 0);
    7.     if (sum % 2 !== 0) {
    8.         return false;
    9.     }
    10.     const halfSum = sum / 2;
    11.     const size = nums.length;
    12.     const dp = Array.from({ length: size + 1 })
    13.         .map(
    14.             _ => Array.from({ length: halfSum + 1 }).map(_ => false)
    15.         );
    16.     for (let i = 0; i <= size; i++) {
    17.         dp[i][0] = true;
    18.     }
    19.     for (let i = 1; i <= size; i++) {
    20.         for (let j = 1; j <= halfSum; j++) {
    21.             if (j - nums[i] < 0) {
    22.                 dp[i][j] = dp[i - 1][j];
    23.             } else {
    24.                 dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j];
    25.             }
    26.         }
    27.     }
    28.     return dp[size][halfSum];
    29. };

    Runtime: 132 ms, faster than 80.28% of JavaScript online submissions for Partition Equal Subset Sum.
    Memory Usage: 40.9 MB, less than 81.51% of JavaScript online submissions for Partition Equal Subset Sum.

    /**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const sum = nums.reduce((prev, current) => prev + current, 0);
    if (sum % 2 !== 0) {
        return false;
    }
    const halfSum = sum / 2;
    const size = nums.length;
    const dp = Array.from({ length: halfSum + 1 }).map(_ => false);
    dp[0] = true;
    for (let i = 1; i <= size; i++) {
        for (let j = halfSum; j > 0; j--) {
            if (j - nums[i] >= 0) {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
    }
    return dp[halfSum];
};