#416

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition Equal Subset Sum

Determine if an array can be partitioned into two subsets with equal sum using dynamic programming techniques.

Problem Statement

Given an integer array nums, determine if it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal. If such a partition is possible, return true; otherwise, return false. The sum of the elements in each subset should be equal, meaning the total sum of the array must be even.

To solve this problem, one needs to determine if there exists a subset of nums that sums up to half of the total sum of the array. This boils down to the subset-sum problem, which can be solved efficiently using dynamic programming.

Examples

Example 1

Input: nums = [1,5,11,5]

Output: true

The array can be partitioned as [1, 5, 5] and [11].

Example 2

Input: nums = [1,2,3,5]

Output: false

The array cannot be partitioned into equal sum subsets.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100

Solution Approach

Dynamic Programming Approach

The key idea is to use dynamic programming to check whether a subset sum equal to half of the total sum exists. We define a DP array where dp[i] means whether a sum of i can be formed from the array. If the total sum is odd, we return false immediately, as it’s impossible to partition an odd sum into two equal parts. We then iterate through the numbers, updating the DP array to reflect which sums can be achieved.

State Transition Optimization

To optimize, we use a bottom-up dynamic programming approach that iterates over the array. Starting from the target sum, we check if the sum can be formed by iterating backward through the possible sums in the DP array. This ensures we don’t reuse the same number in multiple subset calculations, maintaining the correct state transitions.

Time and Space Complexity Optimization

We can reduce space complexity by maintaining only a 1D DP array instead of a 2D one. Instead of storing all possible subset sums for every element, we reuse the DP array, updating values in reverse order to avoid overwriting results that are still needed for the current iteration.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(n * sum), where n is the number of elements in the array and sum is half of the total sum. The space complexity can be reduced to O(sum) by using a 1D DP array.

What Interviewers Usually Probe

Understanding of dynamic programming
Ability to optimize space complexity
Awareness of state transitions in dynamic programming solutions

Common Pitfalls or Variants

Common pitfalls

Assuming the array can always be partitioned without checking if the sum is even
Incorrectly updating the DP array leading to false positives
Not handling edge cases like very small or large numbers in the array correctly

Follow-up variants

If the array contains negative numbers
If the array is sorted or unordered
If there are multiple ways to partition the array

FAQ

What is the primary dynamic programming pattern used to solve the Partition Equal Subset Sum problem?

The primary pattern used is state transition dynamic programming, where we track which subset sums are achievable using an array of possible sums.

How do we handle optimization in the Partition Equal Subset Sum problem?

Optimization is achieved by using a 1D DP array instead of a 2D one and updating it in reverse order to prevent overwriting results in the same iteration.

Can the Partition Equal Subset Sum problem be solved with a greedy approach?

No, the problem cannot be solved with a greedy approach since the partitioning is not guaranteed to follow a simple greedy selection of elements.

What happens if the total sum of the array is odd?

If the total sum is odd, it is immediately impossible to partition the array into two subsets with equal sum, and the answer should be false.

What is the time complexity of the solution?

The time complexity is O(n * sum), where n is the number of elements and sum is half of the total sum of the array.

terminal

Solution

Solution 1: Dynamic Programming

First, we calculate the total sum $s$ of the array. If the total sum is odd, it cannot be divided into two subsets with equal sums, so we directly return `false`. If the total sum is even, we set the target subset sum to $m = \frac{s}{2}$. The problem is then transformed into: does there exist a subset whose element sum is $m$?

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        m, mod = divmod(sum(nums), 2)
        if mod:
            return False
        n = len(nums)
        f = [[False] * (m + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(nums, 1):
            for j in range(m + 1):
                f[i][j] = f[i - 1][j] or (j >= x and f[i - 1][j - x])
        return f[n][m]

Solution 2: Dynamic Programming (Space Optimization)

We notice that in Solution 1, $f[i][j]$ is only related to $f[i - 1][\cdot]$. Therefore, we can compress the two-dimensional array into a one-dimensional array.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        m, mod = divmod(sum(nums), 2)
        if mod:
            return False
        n = len(nums)
        f = [[False] * (m + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(nums, 1):
            for j in range(m + 1):
                f[i][j] = f[i - 1][j] or (j >= x and f[i - 1][j - x])
        return f[n][m]

Continue Practicing

#413 arithmetic slices #410 split array largest sum #403 frog jump