Equal Sum Partition

The problem

Implement `equalSumPartitionProblem(nums)`: given an array of positive integers, return whether it can be split into two subsets with equal sums. Every element must land in exactly one of the two halves.

`[1, 5, 11, 5]` returns `true` — `[11]` and `[1, 5, 5]` both sum to `11`. `[1, 5, 3]` returns `false` — the total is `9`, an odd number, so no split can put the same amount on both sides.

The approach

The reduction is the whole problem. If the two halves have equal sums, each is exactly `total / 2`, so a split exists precisely when some subset sums to `total / 2` — which is `subsetSumProblem` with the target computed instead of handed in. The second half never has to be searched for; whatever the first subset doesn't take *is* the second, and its sum is forced to `total - target = target`.

The parity check comes first and is not an optimisation — it's a correctness guard. An odd total can't be halved into two integer sums, and `sum / 2` would be a fraction, so `Array(target + 1)` would allocate a nonsense length and every index lookup would miss. Returning `false` on `sum % 2 !== 0` before the table exists keeps the DP from ever seeing an input it isn't defined on.

Everything after that is the subset-sum table verbatim: `memo[0][j] = false` (no items, no way to hit a positive target), `memo[i][0] = true` (any prefix can hit `0` by picking nothing), and the same skip-or-take `||` recurrence. The only visible difference is that `target` is now derived from the input rather than a parameter, which also means the table's width scales with the *values* in the array, not with its length.

Worth noting what this returns and what it doesn't: `true` says a partition exists, not which one. Reconstructing the actual subsets means walking the finished table backwards from `memo[n][target]`, stepping to `memo[i-1][j]` when the value came from skipping and to `memo[i-1][j-nums[i-1]]` when it came from taking. The boolean is enough for the question as asked, but the table already holds the answer to the harder version.

The solution

export function equalSumPartitionProblem(nums) {
    const sum = nums.reduce((acc, curr) => acc + curr, 0)
    if (sum % 2 !== 0) return false
    const target = sum / 2
    const memo = Array.from({ length: nums.length + 1 }, () => Array(target + 1).fill(null))

    // initialize the first row with false
    for (let j = 0; j <= target; j++) {
        memo[0][j] = false
    }

    // initialize the first col with true
    for (let i = 0; i <= nums.length; i++) {
        memo[i][0] = true
    }

    // fill the memo table
    for (let i = 1; i <= nums.length; i++) {
        for (let j = 1; j <= target; j++) {
            if (nums[i-1] <= j) {
                memo[i][j] = memo[i-1][j] || memo[i-1][j-nums[i-1]]
            } else {
                memo[i][j] = memo[i-1][j]
            }
        }
    }

    // return the result
    return memo[nums.length][target] === true
}

Time O(n * sum)Space O(n * sum)