416. Partition Equal Subset Sum

February 7, 2022

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.

code

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0: return False
        
        @lru_cache(maxsize=None)
        def dp(i, subset_sum):
            if subset_sum == 0: return True
            if i == len(nums) or subset_sum < 0: return False
            return dp(i + 1, subset_sum - nums[i]) or dp(i + 1, subset_sum)
        
        return dp(0, total_sum // 2)

code written memo

class Solution:
    def canPartition(self, nums):
        s, memo = sum(nums), {0: True}
        if s & 1: return False
        def dp(i, x):
            if x < 0: return False
            if x not in memo:
                memo[x] = False
                for j in range(i, len(nums)):
                    if dp(j+1, x-nums[j]):
                        memo[x] = True
                        break
            return memo[x]
        return dp(0, s >> 1)

code bottom up, dp[i][j] choose from nums[i] to the end, check if exists a subset with sum j

class Solution:
    def canPartition(self, nums):
        s = sum(nums)
        if s & 1: return False
        half = s >> 1
        dp = [([False] * (half + 1)) for _ in range(len(nums) + 1)]
        
        for i in range(len(nums) + 1): 
            dp[i][0] = True 
            
        for i in range(len(nums) - 1, -1, -1):
            for each_sum in range(half + 1):
                if each_sum >= nums[i]:
                    dp[i][each_sum] = dp[i+1][each_sum - nums[i]] or dp[i+1][each_sum]
                else:
                    dp[i][each_sum] = dp[i+1][each_sum]
                
                
        return dp[0][-1]

code

class Solution:
    def canPartition(self, nums):
        s = sum(nums)
        if s & 1: return False
        half = s >> 1
        dp = [False] * (half + 1)
        dp[0] = True            
        for i in range(len(nums) - 1, -1, -1):
            for each_sum in range(half, -1, -1):
                if each_sum >= nums[i]:
                    dp[each_sum] = dp[each_sum] or dp[each_sum - nums[i]]
            if dp[half]: return True
                
        return False

code bottom up, dp[i][j]=true if the sum j can be formed by array elements in subset nums[0]..nums[i],otherwise false

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # find sum of array elements
        total_sum = sum(nums)

        # if total_sum is odd, it cannot be partitioned into equal sum subsets
        if total_sum % 2 != 0:
            return False
        subset_sum = total_sum // 2
        n = len(nums)

        # construct a dp table of size (n+1) x (subset_sum + 1)
        dp = [[False] * (subset_sum + 1) for _ in range(n + 1)]
        dp[0][0] = True
        for i in range(1, n + 1):
            curr = nums[i - 1]
            for j in range(subset_sum + 1):
                if j < curr:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - curr]
        return dp[n][subset_sum]

code dp

after each pass of num

#1 [True, True, False, False, False, False, False, False, False, False, False, False] #5 [True, True, False, False, False, True, True, False, False, False, False, False] #11 [True, True, False, False, False, True, True, False, False, False, False, True] #5 [True, True, False, False, False, True, True, False, False, False, True, True]

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        if total_sum % 2 != 0: return False
        sub_sum = total_sum // 2
        
        dp = [False] * (sub_sum + 1)
        dp[0] = True # without any num the sum is 0
        for cur in nums:
            for j in range(sub_sum, cur - 1, -1):
                dp[j] = dp[j] or dp[j - cur]
            if dp[sub_sum] == True: return True
            
            
        # return dp[sub_sum]        
        return False