416. Partition-Equal-Subset-Sum

Another day, another dynamic programming problem, I would rather e-

Anyways, there’s a very easy initial check to do: We can check if the sum of the entire array is even or odd. If it is odd, we already know that we cannot partition the array into two equal subsets and we can return False early.

Now that we know that the sum is even, we can also easily calculate what each subset should sum up to (total // 2). This is a very simple dynamic programming program (although I initially thought that this would result in the dp array being too large).

The basic idea is that for each number, we have two choices:

• we can either put it in subset A or subset B
• if it is not in one of the subsets, it is guaranteed to be in the other one
• therefore, we can just check if just one of the subset can reach the target sum (once we do, the other subset has also reached the target sum)

So inside dp[i], we can store whether or not we can reach the sum i using the numbers in the array.

So the recurrence relation is:

• base case: dp[0] = True - we can always reach a sum of 0 (just don’t choose any numbers)
• dp[i] = dp[i] or dp[i - num] where num is a number between num and num - 1
  • dp[i] is for the case where we don’t choose the number to be in the subset
  • dp[i - num] is for the case where we do choose the number to be in the subset
  • dp[i] would be true if either of these are true

Then we can just return dp[bag] to check if we can reach the target sum.

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        total = sum(nums)
        
        if total % 2 == 1:
            return False

        bag = total // 2
        dp = [False] * (bag + 1)
        dp[0] = True

        for num in nums:
            for curr in range(bag, num - 1, -1):
                dp[curr] = dp[curr] or dp[curr - num]
        
        return dp[bag]

Time Complexity: O(n * bag)

Space Complexity: O(bag)

Time Taken: too long