LeetCode 416 - Partition Equal Subset Sum

The problem asks whether an array of positive integers can be divided into two subsets such that both subsets have exactly the same sum. Suppose the total sum of all numbers in the array is S.

leetcodemediumarraydynamic-programming

LeetCode Problem 416

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks whether an array of positive integers can be divided into two subsets such that both subsets have exactly the same sum.

Suppose the total sum of all numbers in the array is S. If we want to split the array into two equal subsets, then each subset must sum to S / 2. This immediately gives us an important observation: if the total sum is odd, it is impossible to divide it into two equal integer sums.

For example:

  • nums = [1,5,11,5]

  • Total sum = 22

  • Target subset sum = 11

  • Since we can form a subset with sum 11, the remaining numbers also sum to 11, so the answer is true.

  • nums = [1,2,3,5]

  • Total sum = 11

  • Since 11 is odd, equal partitioning is impossible, so the answer is false.

The input constraints are important:

  • The array length can be up to 200
  • Each number can be up to 100

This means the maximum possible total sum is:

200 * 100 = 20000

A brute force solution that explores every subset would require examining 2^n possibilities, which is far too large for n = 200. However, because the total sum is relatively bounded, dynamic programming based on subset sums becomes feasible.

There are several important edge cases to keep in mind:

  • Arrays with an odd total sum must immediately return false
  • Arrays with only one element can never be partitioned equally
  • Arrays containing repeated values must still be handled correctly
  • Large inputs near the constraint limits require an efficient polynomial-time solution
  • Since all numbers are positive, subset sums only increase, which simplifies the DP logic

Approaches

Brute Force Approach

The brute force method tries every possible subset of the array and checks whether any subset sums to half of the total array sum.

The recursive idea is straightforward:

  • For each number, choose either:

  • include it in the current subset

  • exclude it from the current subset

  • Continue recursively until all numbers are processed

  • If any subset reaches the target sum, return true

This works because every possible subset is explored, so if a valid partition exists, the algorithm will eventually find it.

However, the time complexity is exponential. Each element has two choices, so the total number of subsets is:

2^n

For n = 200, this is completely impractical.

Optimal Dynamic Programming Approach

The key insight is that we do not actually need to enumerate all subsets explicitly.

We only care whether a subset with sum target = total_sum / 2 exists.

This transforms the problem into a classic subset sum problem:

Can we choose some numbers whose sum equals target?

Dynamic programming works well because:

  • The target sum is bounded
  • Subproblems overlap heavily
  • We can build solutions incrementally

We maintain a DP array where:

dp[s] = whether sum s is achievable

Initially:

  • dp[0] = true, because sum 0 is always possible using an empty subset

For each number:

  • Update the DP array backwards
  • If dp[s - num] is true, then dp[s] can also become true

The backward iteration is extremely important because it prevents reusing the same element multiple times in a single iteration.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every subset recursively
Optimal Dynamic Programming O(n * target) O(target) Uses subset sum DP with rolling state

Algorithm Walkthrough

Optimal DP Algorithm

  1. Compute the total sum of the array.

We first add all numbers together. If the total sum is odd, we immediately return false because two equal integer subsets are impossible. 2. Compute the target subset sum.

Since the two subsets must have equal sums:

target = total_sum // 2

The problem now becomes determining whether any subset sums to target. 3. Create a DP array.

We create a boolean array of size target + 1.

dp[s] = whether sum s can be formed

Initially:

dp[0] = true

because an empty subset can always produce sum 0. 4. Process each number in the array.

For every number num, we update the DP array from right to left.

Backward iteration is necessary because each number can only be used once. If we iterate forward, the same number could contribute multiple times during the same iteration. 5. Update reachable sums.

For every sum s from target down to num:

  • If dp[s - num] is already true,
  • then we can also form sum s

So:

dp[s] = dp[s] OR dp[s - num]
  1. Return the final result.

After processing all numbers:

  • If dp[target] is true, a valid partition exists
  • Otherwise, it does not

Why it works

The DP invariant is:

After processing the first i numbers, dp[s] is true if and only if some subset of those numbers sums to s.

Initially, only sum 0 is achievable. Each new number either contributes to a new sum or does not. By iteratively updating reachable sums, the algorithm eventually captures every achievable subset sum exactly once. Therefore, dp[target] correctly determines whether an equal partition exists.

Python Solution

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)

        # Equal partition is impossible if total sum is odd
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2

        # dp[s] indicates whether sum s is achievable
        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            # Iterate backwards to avoid reusing the same number
            for current_sum in range(target, num - 1, -1):
                if dp[current_sum - num]:
                    dp[current_sum] = True

        return dp[target]

The implementation begins by computing the total sum of the array. If the sum is odd, the function immediately returns False because equal partitioning is mathematically impossible.

Next, the target subset sum is computed as half of the total sum. The DP array is then initialized, where each index represents whether a particular sum is achievable.

The algorithm processes each number one at a time. For every number, it iterates backward through the DP array. This backward traversal ensures that each number is only used once per subset calculation.

Whenever a previously reachable sum current_sum - num exists, the current sum becomes reachable as well.

Finally, the function returns whether the target sum is achievable.

Go Solution

func canPartition(nums []int) bool {
	totalSum := 0

	for _, num := range nums {
		totalSum += num
	}

	// Equal partition is impossible if total sum is odd
	if totalSum%2 != 0 {
		return false
	}

	target := totalSum / 2

	// dp[s] indicates whether sum s is achievable
	dp := make([]bool, target+1)
	dp[0] = true

	for _, num := range nums {
		// Iterate backwards to avoid reusing the same number
		for currentSum := target; currentSum >= num; currentSum-- {
			if dp[currentSum-num] {
				dp[currentSum] = true
			}
		}
	}

	return dp[target]
}

The Go implementation follows exactly the same logic as the Python solution.

Slices are used instead of Python lists, and boolean values default to false, which simplifies initialization. Integer overflow is not a concern here because the maximum possible sum is only 20000, well within Go's integer range.

The backward iteration remains critical in Go as well, ensuring each number contributes at most once per subset calculation.

Worked Examples

Example 1

nums = [1,5,11,5]

Total sum:

1 + 5 + 11 + 5 = 22

Target:

22 / 2 = 11

Initial DP state:

Sum 0 1 2 3 4 5 6 7 8 9 10 11
Reachable T F F F F F F F F F F F

Process number 1

Reachable sums:

  • 1 becomes reachable from 0
Sum 0 1 2 3 4 5 6 7 8 9 10 11
Reachable T T F F F F F F F F F F

Process number 5

New reachable sums:

  • 5 from 0
  • 6 from 1
Sum 0 1 2 3 4 5 6 7 8 9 10 11
Reachable T T F F F T T F F F F F

Process number 11

New reachable sums:

  • 11 from 0
Sum 0 1 2 3 4 5 6 7 8 9 10 11
Reachable T T F F F T T F F F F T

Since dp[11] = true, the answer is true.

Example 2

nums = [1,2,3,5]

Total sum:

1 + 2 + 3 + 5 = 11

Since 11 is odd, the algorithm immediately returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n * target) Each number processes all sums up to target
Space O(target) One DP array of size target + 1

The DP array contains target + 1 entries, where target is half of the total sum. Since the maximum total sum is 20000, the maximum target is 10000, which is manageable.

For every element in the array, the algorithm iterates through all possible sums up to the target. Therefore, the overall time complexity is O(n * target).

Test Cases

solution = Solution()

assert solution.canPartition([1, 5, 11, 5]) == True   # Standard valid partition
assert solution.canPartition([1, 2, 3, 5]) == False   # Odd total sum

assert solution.canPartition([2, 2]) == True          # Two equal elements
assert solution.canPartition([1]) == False            # Single element

assert solution.canPartition([1, 1]) == True          # Smallest valid partition
assert solution.canPartition([100, 100]) == True      # Large equal values

assert solution.canPartition([1, 2, 5]) == False      # Cannot reach target sum
assert solution.canPartition([3, 3, 3, 4, 5]) == True # Multiple subset choices

assert solution.canPartition([2, 2, 3, 5]) == False   # Close but impossible
assert solution.canPartition([1, 2, 3, 4, 5, 6, 7]) == True # Larger valid case

assert solution.canPartition([10, 10, 10, 10]) == True # Repeated numbers
assert solution.canPartition([1] * 200) == True        # Maximum length stress test
Test Why
[1,5,11,5] Standard successful partition
[1,2,3,5] Odd total sum
[2,2] Small equal pair
[1] Single-element edge case
[1,1] Smallest successful partition
[100,100] Large equal values
[1,2,5] Target sum unreachable
[3,3,3,4,5] Multiple valid combinations
[2,2,3,5] No valid subset despite even sum
[1,2,3,4,5,6,7] Larger balanced partition
[10,10,10,10] Repeated values
[1] * 200 Maximum-length stress test

Edge Cases

One important edge case occurs when the total sum is odd. Many incorrect solutions waste time attempting DP or recursion even though equal partitioning is mathematically impossible. The implementation handles this immediately with:

if total_sum % 2 != 0:
    return False

Another important case is arrays with only one element. A single positive number cannot be split into two non-empty subsets with equal sums. The algorithm naturally handles this because either the total sum is odd or the target sum cannot be formed.

A third tricky case involves repeated values. For example:

[10,10,10,10]

Incorrect DP implementations that iterate forward may accidentally reuse the same element multiple times in one iteration. This implementation iterates backward, ensuring each number is only used once.

Another subtle edge case is when the target sum exists in multiple ways. For example:

[3,3,3,4,5]

The DP approach correctly tracks all reachable sums simultaneously, so it does not depend on discovering a specific subset ordering.

Finally, large stress-test inputs near the constraints require efficient memory usage. Using a one-dimensional DP array reduces space complexity from O(n * target) to O(target), making the solution practical even for the largest valid inputs.