LeetCode 416: Partition Equal Subset Sum

Problem Description

LeetCode Problem 416

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

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.

Constraints:

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

Difficulty: Medium

Tags: array, dynamic programming

Rating: 97.98%

Solution

Here’s my Python solution to this problem:

#Problem 416: Partition Equal Subset Sum

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        s = sum(nums)
        if s % 2 != 0: return False

        t = s // 2

        dp = [False] * (t+1)
        dp[0] = True

        for n in nums:
            # We iterate from t to n-1 because we don't want to consider the same element twice
            for j in range(t, n-1, -1):
                # If we can make the sum j-n, we can make the sum j
                dp[j] = dp[j] or dp[j-n]

        return dp[t]

Key Insights

1. If the total sum is odd, it’s impossible to split into equal halves
2. We only need to find one subset that sums to half the total - the other subset will automatically have the same sum
3. This is a variation of the 0/1 knapsack problem using dynamic programming

Solution Walkthrough

Let’s solve this step by step using the example: nums = [1, 5, 11, 5]

Step 1: Initial Checks

s = sum(nums)  # s = 22
if s % 2 != 0: return False
t = s // 2     # t = 11 (our target sum)

Step 2: DP Array Setup

• We create a boolean array dp of size t + 1
• dp[i] represents whether we can make sum i using some elements from the array
• Initially, only dp[0] = True (we can always make sum 0 by selecting no elements)

Initial dp: [T, F, F, F, F, F, F, F, F, F, F, F]
           [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

Step 3: Building the DP Array

For each number in our input array, we update the dp array:

1. First number (1):

dp: [T, T, F, F, F, F, F, F, F, F, F, F]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

2. Second number (5):

dp: [T, T, F, F, F, T, T, F, F, F, F, F]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

3. Third number (11):

dp: [T, T, F, F, F, T, T, F, F, F, F, T]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

4. Fourth number (5):

dp: [T, T, F, F, F, T, T, F, F, F, T, T]
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

Key Line Explanation

dp[j] = dp[j] or dp[j-n]

This line means:

• We can make sum j if either:
  1. We could already make sum j before (dp[j])
  2. We could make sum j-n and add the current number n

Why Iterate Backwards?

for j in range(t, n-1, -1)

We iterate backwards because:

• We want to use each number only once
• If we went forward, we might use the same number multiple times
• By going backwards, we ensure we only use new information from the previous iteration

Example Partitions

For our example [1, 5, 11, 5]:

• Target sum = 11
• One valid partition is:
  • Subset 1: [1, 5, 5] = 11
  • Subset 2: [11] = 11

Space and Time Complexity

• Time Complexity: $O(n * target)$ = $O(n * sum(nums)/2)$ = $O(n^2)$
• Space Complexity: $O(target)$ = $O(sum(nums)/2)$ = $O(n)$