Partition Equal Subset Sum

Explanation & Solution

Description

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

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

Output: true

Explanation: The array can be partitioned as [1,5,5] and [11], both summing to 11.

Constraints

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

Approach

Dynamic Programming pattern

1. Check the Total Sum

Compute the total sum of all elements in nums
If the total is odd, return false immediately — you cannot split an odd sum into two equal integer halves

2. Define the Target

Set target = total / 2
The problem reduces to: can we find a subset of nums that sums to exactly target?

3. Initialize the DP Array

Create a boolean array dp of size target + 1, initialized to false
Set dp[0] = true because a sum of 0 is always achievable (empty subset)

4. Process Each Number

For each number num in nums, iterate j from target down to num
Update dp[j] = dp[j] || dp[j - num] — either we already can form sum j without this number, or we can form it by adding this number to a subset that sums to j - num
Iterating backwards ensures each number is used at most once

5. Return the Result

dp[target] tells us whether a subset summing to exactly target exists
If true, the remaining elements also sum to target, giving an equal partition

Key Insight

This problem is a variant of the 0/1 Knapsack problem where we check if a subset sum equals half the total
The 1D DP with reverse iteration keeps space at O(target)
Time complexity is **O(n * target)** where n is the array length and target is half the total sum

Visualization

Input:

Dynamic Programmingnums = [1,5,11,5]

Press play to start DP animation

ComputingDependencyFilledEmpty

7 steps

Solution Code

0/1 Knapsack

Decode Ways