Course contentsShow
← Computer Science
Lesson 933 of 2,87222. Dynamic ProgrammingFree lesson

Partition Equal Subset Sum

Check if an array can be partitioned into two subsets with equal sum using subset sum DP.

Partition Equal Subset Sum

You'll learn how to check if an array can be split into two subsets with equal sums using dynamic programming.

Imagine you have a bag of coins with different values and you want to divide them into two piles that have exactly the same total value. That's the partition equal subset sum problem!

The Core Idea

Given an array of positive integers, determine whether you can partition it into two subsets where both subsets have the same sum.

Key insight: If the total sum is odd, it's impossible—you can't split an odd number equally. If the sum is even, you need to find a subset that adds up to exactly sum / 2. If such a subset exists, the remaining elements automatically form the other half.

This reduces to the Subset Sum Problem you already know! You're just checking if there's a subset with sum equal to half the total.

Why Dynamic Programming?

You have overlapping subproblems: "Can I make sum S using the first N items?" gets asked repeatedly with different values of S and N. Memoization or tabulation helps avoid recalculating the same questions.

The Approach

  1. Calculate the total sum of the array
  2. If it's odd, return false immediately
  3. Set target = sum / 2
  4. Use the subset sum DP solution to check if you can achieve the target sum
  5. Your DP state: dp[i][j] = "can we make sum j using first i elements?"

Key Takeaway: Partition Equal Subset Sum cleverly transforms into Subset Sum by recognizing that finding one half automatically gives you both halves—just check if you can make totalSum / 2 using the existing subset sum DP approach.