Partition Equal Subset Sum - Python Solution

1. Introduction

"Partition Equal Subset Sum" is a problem that falls under the category of dynamic programming and combinatorial optimization. It involves determining whether a given set of numbers can be partitioned into two subsets with equal sums. This problem is an excellent example of the knapsack problem and is useful for understanding how to partition sets in an optimized way.

Problem

Given an integer array nums, the objective is to return true if the array can be partitioned into two subsets such that the sum of the elements in both subsets is equal, or false otherwise.

2. Solution Steps

1. Calculate the total sum of the array. If the sum is odd, return false as it cannot be partitioned into two equal subsets.

2. Set the target sum for each subset as half of the total sum.

3. Use a dynamic programming approach to check if there's a subset with the target sum.

4. Initialize a boolean array dp with a length of target sum + 1 to store whether a sum is achievable.

5. Set the base case dp[0] = true (sum of 0 is always achievable).

6. Iterate over the numbers and update the dp array for each number.

7. Check if the target sum is achievable by the end of the array.

8. Return true if the target sum is achievable, otherwise false.

3. Code Program

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]

    return dp[target]

# Example Usage
print(canPartition([1, 5, 11, 5]))
print(canPartition([1, 2, 3, 5]))

Output:

True
False

Explanation:

1. Sum Calculation: The total sum of the array is computed first. If it's odd, partitioning into two equal subsets is impossible.

2. Target Sum: The target sum for each subset is set as half of the total sum.

3. Dynamic Programming Array: dp array keeps track of the sums that are achievable with the current set of numbers.

4. Subset Sum Calculation: The function iteratively checks if each number can contribute to achieving the target sum.

5. Final Check: By the end of the array, dp[target] indicates whether the target sum is achievable.

6. Result: The function returns true if partitioning into two subsets with equal sums is possible, else false.