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

`.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}recursion(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 / 25
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 true12    if (remainingSum < 0 || iNum >= nums.length) return false13
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 || skipCurrentNumber19
20    memo[iNum][remainingSum] = res21
22    return res23  }24
25  return recursion(halfSum)26}```

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

## Tags

leetcode

recursion

dynamic programming

## Next Post

LeetCode: Top K Frequent Words

Oct 19, 2022

Hash and sort

Search Posts