Leetcode - Partition Equal Subset Sum

Question

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Idea

• Using a bottom-up Tabulation approach like we do with Leetcode - Word Break
• Keep a set cache for our dp, where we want to iterate throughout our numbers array, where on each number, we want to compute and store the sum of that number and each of the existing numbers in our cache which will store all potential sums that we can create using this array
• If we find our target which is the sum of the array // 2 in the cache, then we return true, otherwise return False
• Also if the total sum is not even, return False right away since we can’t physically make that sum with an even (2) partition

Solution