LC416 - Partition Equal Subset Sum

Problem

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.

Example

Input: nums = [1,5,11,5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Solution

Intuition

Sum array and check if divisible by two to see if possible initially. If it is, the target sum for each subset will be half the total sum. Create a set of possible sums from the entire array (kind of similar to SLP tokenization) and check if target contained in set. If so, return True, else return False. Time and space complexity of this approach is $O(n^2)$.

def canPartition(self, nums: List[int]) -> bool:
	target = sum(nums)/2
	# If target is not integer, not possible.
	if not target.is_integer():
		return False

	possibleSums = {0}
	
	for num in nums:
		tempSet = set()
		for possibleSums in possibleSums:
			possibleSums.add(num+possibleSum)
		possibleSums = possibleSums.union(tempSet)

	if target in possibleSums:
		return True
	else:
		return False