Skip to main content

Partition Equal Subset Sum

Question​

None

Example 1
None

Solution​

all//Partition Equal Subset Sum.py


#Partition Equal Subset Sum Algorithm
#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.

def canPartition(nums):
    total_sum = sum(nums)

    #check if total sum is even
    if total_sum % 2 != 0:
        return False

    #find target sum
    target_sum = total_sum // 2

    #create a 2D boolean array
    dp = [[False for _ in range(target_sum + 1)]
            for _ in range(len(nums) + 1)]

    #initialize first row and column to true
    for i in range(len(dp)):
        dp[i][0] = True
    for j in range(1, target_sum + 1):
        dp[0][j] = False

    #populate 2D array
    for i in range(1, len(dp)):
        for j in range(1, target_sum + 1):
            if j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

    #return last element
    return dp[-1][-1]

nums = [1,5,11,5]
print(canPartition(nums))
#output: True