Devin's Blog

Partition Equal Subset Sum

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • Sum of elements of both subsets being equal means both subsets must have the sum(elements) // 2, and if one subset has a sum(elements) // 2 sum, then the other must have the same.
  • Therefore, for each element, we check:
    • Should I include this element in the current subset or not?
  • In a bottom up approach, we store the sum of each subset such that we get less space.

Complexity

Runtime

  • This gives a memory limit expiration for top down since it takes up too much memory to store every possible sum for an array of size 200.
  • )
    • For each element, we check if we keep the element in the subset or not.
    • We have a set to keep track of all the sums before, such that we can have less memory.

Space

  • We have to store that many items in the worst case wherein we find no elements that are equal.

Code

Bottom Up

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False
 
        sums = set([0])
        target = sum(nums) // 2
        for i in range(len(nums)):
            tmp = set()
            for cur_sum in sums:
                new_sum = nums[i] + cur_sum
                if new_sum == target:
                    return True
                tmp.add(cur_sum)
                tmp.add(new_sum)
            sums = tmp
 
        return False

Top Down (MLE)

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        # If not even
        if total % 2 != 0:
            return False
        
        n = len(nums)
        @cache
        def r(i, remaining):
            if remaining == 0:
                return True
            if i >= n or remaining < 0:
                return False
            
            include = r(i + 1, remaining - nums[i])
            not_include = r(i + 1, remaining)
            if include or not_include:
                return True
            return False
 
        return r(0, total // 2)

Cards

START Basic Front: Partition Equal Subset Sum Back: Should I include this element in the current subset or not such that the subset equals total // 2?

END

References

Graph View