416. partition equal subset sum

3 min read 21-10-2024

Cracking the Code: Partition Equal Subset Sum

The "Partition Equal Subset Sum" problem, famously known as problem 416 on LeetCode, is a classic example of a dynamic programming problem. It challenges you to determine if a given array of positive integers can be partitioned into two subsets with equal sums.

Let's break down the problem, explore a solution using dynamic programming, and learn how to implement it efficiently.

Understanding the Problem

Imagine you have a set of coins with different values, and you want to split them into two piles with the same total value. Can you do it? This is essentially the core of the Partition Equal Subset Sum problem.

Formal Definition:

Given an array of positive integers nums, determine if it can be partitioned into two subsets with equal sums.

Example:

Input: nums = [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned into [1, 5, 5] and [11].

Dynamic Programming Approach

Dynamic programming shines when dealing with problems that can be broken down into overlapping subproblems. In this case, our subproblems involve determining if a subset with a specific sum can be formed from the first i elements of the array.

Key Idea:

We'll build a 2D table dp where dp[i][j] represents whether a subset with sum j can be formed using the first i elements of the nums array.

Initialization:

dp[0][j] = False for all j > 0 (No elements, cannot form a non-zero sum).
dp[i][0] = True for all i (We can always form a subset with sum 0).

Iteration:

For each element i in nums:

For each target sum j:
- If the current element nums[i] is less than or equal to the target sum j:
  - dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]].
  - In other words, dp[i][j] is true if either:
    - We can form a subset with sum j using the previous elements (excluding the current element).
    - We can form a subset with sum j-nums[i] using the previous elements, and then include the current element.

Final Check:

Return dp[n][sum//2], where n is the length of nums and sum is the total sum of all elements.

Example:

Let's visualize the dp table for the example nums = [1, 5, 11, 5]:

  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
--|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | T | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F |
1 | T | T | F | F | F | T | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F | F |
2 | T | T | F | F | F | T | F | F | F | F | F | T | F | F | F | T | F | F | F | F | F | F | F | F |
3 | T | T | F | F | F | T | F | F | F | F | F | T | F | F | F | T | F | F | F | F | F | F | F | T |
4 | T | T | F | F | F | T | F | F | F | F | F | T | F | F | F | T | F | F | F | F | F | F | F | T |

We can see that dp[4][11] is True, indicating that a subset with sum 11 (which is half of the total sum) can be formed using the elements of the array.

Code Implementation (Python)

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

    # If the total sum is odd, it cannot be partitioned equally
    if total_sum % 2 != 0:
        return False

    # Initialize the dp table
    dp = [[False for _ in range(total_sum // 2 + 1)] for _ in range(n + 1)]

    # Base case: No elements can form a sum of 0
    for i in range(n + 1):
        dp[i][0] = True

    # Iterate through the array and target sums
    for i in range(1, n + 1):
        for j in range(1, total_sum // 2 + 1):
            if nums[i - 1] <= j:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
            else:
                dp[i][j] = dp[i - 1][j]

    # Return the result
    return dp[n][total_sum // 2]

# Example usage
nums = [1, 5, 11, 5]
print(canPartition(nums))  # Output: True

Optimization

The space complexity of the above implementation is O(n * sum), where n is the length of the array and sum is the total sum. We can optimize the space complexity to O(sum) by observing that we only need the previous row of the dp table to calculate the current row. This leads to a more memory-efficient solution.

Conclusion

The "Partition Equal Subset Sum" problem is a fundamental problem in dynamic programming. Understanding its solution provides a strong foundation for solving similar problems involving partitioning or finding subsets with specific properties. Remember, dynamic programming is all about breaking down problems into smaller, overlapping subproblems and building up the solution step-by-step.