LeetCode: Partition Equal Subset Sum Solution

Approach

Let recursion(sum, i) is the possibility of having a subset that sums up to sum in the range 0..i

Pseudo:

1recursion(sum, i) = pickCurrentNumber || skipCurrentNumber

Implementation

1var canPartition = function (nums) {
2  const sum = nums.reduce((acc, el) => acc + el, 0)
3  if (sum % 2 !== 0) return false
4  const halfSum = sum / 2
5
6  const memo = Array.from({ length: nums.length }, _ =>
7    Array(halfSum).fill(null)
8  )
9
10  const recursion = (remainingSum, iNum = 0) => {
11    if (remainingSum === 0) return true
12    if (remainingSum < 0 || iNum >= nums.length) return false
13
14    if (memo[iNum][remainingSum] != null) return memo[iNum][remainingSum]
15
16    const pickCurrentNumber = recursion(remainingSum, iNum + 1)
17    const skipCurrentNumber = recursion(remainingSum - nums[iNum], iNum + 1)
18    const res = pickCurrentNumber || skipCurrentNumber
19
20    memo[iNum][remainingSum] = res
21
22    return res
23  }
24
25  return recursion(halfSum)
26}

References

Original problem

Similar problems

Partition to K Equal Sum Subsets

Minimize the Difference Between Target and Chosen Elements

Maximum Number of Ways to Partition an Array

Partition Array Into Two Arrays to Minimize Sum Difference

Find Subarrays With Equal Sum