# LeetCode: Partition Equal Subset Sum Solution

*Memoized recursion*

## 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 false4 const halfSum = sum / 256 const memo = Array.from({ length: nums.length }, _ =>7 Array(halfSum).fill(null)8 )910 const recursion = (remainingSum, iNum = 0) => {11 if (remainingSum === 0) return true12 if (remainingSum < 0 || iNum >= nums.length) return false1314 if (memo[iNum][remainingSum] != null) return memo[iNum][remainingSum]1516 const pickCurrentNumber = recursion(remainingSum, iNum + 1)17 const skipCurrentNumber = recursion(remainingSum - nums[iNum], iNum + 1)18 const res = pickCurrentNumber || skipCurrentNumber1920 memo[iNum][remainingSum] = res2122 return res23 }2425 return recursion(halfSum)26}

## References

## 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

## Comments

Loading comments...

## Tags

leetcode

recursion

dynamic programming

## Apply and earn a $2,500 bonus once you're hired on your first job!

Clients from the Fortune 500 to Silicon Valley startups

Choose your own rate, get paid on time

From hourly, part-time, to full-time positions

Flexible remote working environment

A lot of open JavaScript jobs!!

**Fact corner:** Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.

**Still hesitate?** Read HoningJS author's guide on dealing with Toptal interview process.