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

Comments

Loading comments...

Tags

leetcode

recursion

dynamic programming

Next Post

LeetCode: Top K Frequent Words

Oct 19, 2022

Hash and sort

Previous Post

HoningJS

Search Posts