Partition Equal Subset Sum in DSA Typescript

Mental Model

We want to split a list of numbers into two groups with the same total sum. This means finding if there's a subset that adds up to half the total sum.

Analogy: Imagine you have a pile of coins and want to divide them into two equal piles. You try to find some coins that together make exactly half the total value.

Array: [1, 5, 11, 5]
Total sum = 22
Target subset sum = 11
We look for a subset that sums to 11.

Subset sum table (partial):
Index -> 0 1 2 3 4
Sum ->  0 1 5 11 16

We check if sum 11 is possible using some elements.

Dry Run Walkthrough

Input: list: [1, 5, 11, 5]

Goal: Find if we can split the list into two subsets with equal sum (11 each).

Step 1: Calculate total sum = 1 + 5 + 11 + 5 = 22, target subset sum = 11

Total sum = 22, target = 11

Why: We need to find a subset with sum equal to half the total to split equally.

Step 2: Initialize a boolean array dp of size target+1 with dp[0] = true

dp = [true, false, false, false, false, false, false, false, false, false, false, false]

Why: dp[s] means if sum s can be formed from some subset.

Step 3: Process number 1: update dp for sums that include 1

dp after 1: [true, true, false, false, false, false, false, false, false, false, false, false]

Why: We can form sum 1 using the number 1.

Step 4: Process number 5: update dp for sums that include 5

dp after 5: [true, true, false, false, false, true, true, false, false, false, false, false]

Why: We can form sums 5 and 6 (1+5) now.

Step 5: Process number 11: update dp for sums that include 11

dp after 11: [true, true, false, false, false, true, true, false, false, false, false, true]

Why: We can form sum 11 directly.

Step 6: Process number 5: update dp for sums that include this 5

dp after second 5: [true, true, false, false, false, true, true, false, false, false, true, true]

Why: We can form sum 10 (5+5) and sum 11 remains possible.

Result:

dp[11] = true means subset sum 11 is possible.
So, the list can be partitioned into two equal subsets.
Answer: true

Annotated Code

DSA Typescript

class PartitionEqualSubsetSum {
  static canPartition(nums: number[]): boolean {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false; // odd sum can't split equally
    const target = total / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true; // zero sum is always possible

    for (const num of nums) {
      for (let s = target; s >= num; s--) {
        dp[s] = dp[s] || dp[s - num]; // update dp for current num
      }
    }
    return dp[target];
  }
}

// Driver code
const nums = [1, 5, 11, 5];
console.log(PartitionEqualSubsetSum.canPartition(nums));

if (total % 2 !== 0) return false; // odd sum can't split equally

Check if total sum is even; if not, partition is impossible

dp[0] = true; // zero sum is always possible

Initialize dp to mark sum 0 as achievable

for (const num of nums) {

Iterate over each number to update possible sums

for (let s = target; s >= num; s--) {

Traverse sums backward to avoid using the same number multiple times

dp[s] = dp[s] || dp[s - num]; // update dp for current num

Mark sum s achievable if sum s-num was achievable before

return dp[target];

Return if target sum is achievable

Output

true

Complexity Analysis

Time: O(n * sum) because we check each number against all sums up to half the total

Space: O(sum) because we use a dp array of size half the total sum

vs Alternative: Naive approach tries all subsets with exponential time; DP reduces it to polynomial time

Edge Cases

Empty list

Returns true because empty subsets trivially partition equally

DSA Typescript

dp[0] = true; // zero sum is always possible

List with one element

Returns false because one element can't be split into two equal subsets

DSA Typescript

if (total % 2 !== 0) return false; // odd sum can't split equally

List with all elements zero

Returns true because sum is zero and subsets can be equal

DSA Typescript

dp[0] = true; // zero sum is always possible

When to Use This Pattern

When asked if a list can be split into two equal sum subsets, use the subset sum dynamic programming pattern to check if half the total sum is achievable.

Common Mistakes

Mistake: Iterating dp array forward causing reuse of the same element multiple times
Fix: Iterate dp array backward to avoid counting the same element more than once

Mistake: Not checking if total sum is even before proceeding
Fix: Add a check to return false immediately if total sum is odd

Summary

Checks if a list can be split into two subsets with equal sum by finding a subset with half the total sum.

Use when you need to partition a set into two equal sum parts or check subset sums.

The key insight is that partitioning into equal subsets means finding a subset with sum equal to half the total.