Problem: Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1:
Input: nums =[1, 5, 11, 5]
Output: True
Explanation: The array can be partitioned as [1,5,5] and [11].
Example 2:
Input: nums =[1,2,3,5]
Output: False
Explanation: The array cannot be partitioned into equal sum subsets.
Solution
from typing import Listimport unittestclass Solution:def canPartition(self, nums: List[int])->bool: if sum(nums) % 2: return False dp =set() # we are guaranteed that we can add up to a sum of zero if we don't choose # any value from the input array nums dp.add(0) target =sum(nums) //2 for i in range(len(nums)-1, -1, -1): nextDP = set() for t in dp: # return it the first time we find the target to improve time complexity if(t + nums[i]) == target: return True nextDP.add(t + nums[i]) nextDP.add(t) dp = nextDP return True if target in dp else FalseTesting
Here's a unit test to evaluate the above piece of code.
class TestPartitionEqualSubsetSum(unittest.TestCase): def __init__(self, methodName: str = "runTest") -> None: super().__init__(methodName) self.sol = Solution() def test_can_partition_equal_subset_sum(self): self.assertEqual(True, self.sol.canPartition([1, 5, 11, 5])) self.assertEqual(False, self.sol.canPartition([1,2,3,5]))if __name__=="__main__":unittest.main()
Solution: Approach 2
I thought this is a simple approach to this problem. However, I am looking forward to a fruitful engagement on whether this solution does hold!
def partition_equal_subset_sum(arr): if sum(arr) % 2 ==0: return True else: return FalseTesting: Solution 2
Here's a unit test for the second solution.
class TestPartitionEqualSubsetSumTwo(unittest.TestCase): def __init__(self, methodName: str = "runTest") -> None: super().__init__(methodName) def test_can_partition_equal_subset_sum(self): self.assertEqual(True, partition_equal_subset_sum([1, 5, 11, 5])) self.assertEqual(False, partition_equal_subset_sum([1,2,3,5]))if __name__=="__main__":unittest.main()