Partition Equal Subset Sum medium

Problem Statement

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.

Steps

1. Calculate the total sum: Find the sum of all elements in the input array nums. If the sum is odd, it's impossible to partition the array into two subsets with equal sums, so return False.

2. Target sum: The target sum for each subset is total_sum // 2.

3. Dynamic Programming: We'll use dynamic programming to determine if a subset with the target sum can be formed. Create a DP table (a boolean array) of size target_sum + 1. dp[i] will be True if a subset with sum i can be formed using elements from nums, and False otherwise.

4. Initialize DP table: dp[0] = True because an empty subset always has a sum of 0.

5. Iterate through nums: For each number num in nums, iterate through the DP table from target_sum down to num. If dp[i - num] is True (meaning a subset with sum i - num exists), then we can include num to form a subset with sum i. Therefore, set dp[i] = True.

6. Check the result: After iterating through all numbers in nums, dp[target_sum] will be True if a subset with the target sum exists, and False otherwise. Return dp[target_sum].

Explanation

The dynamic programming approach efficiently explores all possible combinations of subsets. Instead of explicitly generating all subsets (which would be exponential time complexity), it cleverly builds up a solution from smaller subproblems. dp[i] represents the solvability of a smaller subproblem: can we create a subset with sum i using a subset of the numbers we've processed so far? By iterating through the numbers and updating the DP table accordingly, we can determine if a subset with the target sum is achievable without redundant calculations.

Code

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

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

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

    return dp[target_sum]

Complexity

• Time Complexity: O(N*S), where N is the length of nums and S is the sum of elements in nums. This is because we iterate through nums once, and for each number, we iterate through a portion of the DP table.
• Space Complexity: O(S), where S is the sum of elements in nums. This is the space used by the DP table.