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.

Practice

1. What does the Partition Equal Subset Sum problem ask you to find?

easy

A. If the array can be split into two subsets with equal sums

B. If the array contains any duplicate elements

C. If the array is sorted in ascending order

D. If the array has an even number of elements

Solution

1. Step 1: Understand the problem goal

   The problem asks whether the given array can be divided into two parts where the sum of elements in both parts is the same.

2. Step 2: Clarify what is being checked

   It is not about duplicates, sorting, or count of elements, but about equal sum partitioning.

3. Final Answer:

   If the array can be split into two subsets with equal sums -> Option A

4. Quick Check:

   Partition Equal Subset Sum = Split into equal sum subsets [OK]

Hint: Focus on equal sum subsets, not element order or duplicates [OK]

Common Mistakes:

• Thinking it checks for duplicates
• Confusing with sorting problems
• Assuming it checks array length parity

2. Which of the following TypeScript function signatures correctly represents a function to solve Partition Equal Subset Sum?

easy

A. function canPartition(nums: boolean[]): boolean

B. function canPartition(nums: string): number

C. function canPartition(nums: number): string

D. function canPartition(nums: number[]): boolean

Solution

1. Step 1: Identify correct parameter type

   The input is an array of numbers, so nums: number[] is correct.

2. Step 2: Identify correct return type

   The function returns true or false, so return type is boolean.

3. Final Answer:

   function canPartition(nums: number[]): boolean -> Option D

4. Quick Check:

   Input array of numbers, output boolean [OK]

Hint: Input is number array, output is boolean for yes/no [OK]

Common Mistakes:

• Using wrong input type like string or boolean array
• Returning number instead of boolean
• Incorrect function signature syntax

3. What is the output of the following TypeScript code?

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
}

console.log(canPartition([1, 5, 11, 5]));

medium

A. Runtime error

B. true

C. undefined

D. false

Solution

1. Step 1: Calculate total sum and check parity

   The sum is 1+5+11+5 = 22, which is even, so continue.

2. Step 2: Use dynamic programming to check subset sum

   The code checks if a subset sums to 11 (half of 22). The subset [11] or [5,5,1] sums to 11, so dp[11] becomes true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Sum even and subset exists = true [OK]

Hint: Check if half sum subset exists using dp array [OK]

Common Mistakes:

• Not checking if total sum is even
• Confusing dp array update direction
• Assuming false because of large numbers

4. Find the bug in this TypeScript code for Partition Equal Subset Sum:

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let j = num; j <= target; j++) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
}

medium

A. Missing initial value in reduce causes error on empty array

B. dp array size is incorrect

C. Loop direction in inner for loop should be reversed

D. No bug, code is correct

Solution

1. Step 1: Check reduce usage

   Reduce lacks initial value, but if array is non-empty, it works. Not the main bug.

2. Step 2: Check inner loop direction

   The inner loop runs from num to target increasing, but it should run backward from target down to num to avoid using updated dp values in the same iteration.

3. Final Answer:

   Loop direction in inner for loop should be reversed -> Option C

4. Quick Check:

   Inner loop must go backward to avoid dp overwrite [OK]

Hint: Inner loop for dp must run backward to prevent reuse [OK]

Common Mistakes:

• Not reversing inner loop causes wrong dp updates
• Assuming reduce always needs initial value
• Ignoring dp array size correctness

5. Given the array [2, 2, 3, 7], which of the following subsets can be one half of the partition if the array can be split into two equal sum subsets?

hard

A. [2, 2, 3]

B. [2, 3]

C. [5]

D. [3, 5]

Solution

1. Step 1: Calculate total sum

   Sum = 2 + 2 + 3 + 7 = 14. Half sum = 7.

2. Step 2: Find subset summing to 7

   Check each option:
   A: [2,3] = 5 ≠ 7
   B: [2,2,3] = 7 == 7
   C: [5] = 5 ≠ 7 (5 not in array)
   D: [3,5] = 8 ≠ 7 (5 not in array)
   B works, with remaining [7] also 7.

3. Final Answer:

   [2, 2, 3] -> Option A

4. Quick Check:

   Sum half is 7, B sums to 7 [OK]

Hint: Sum array, find subset with half sum [OK]

Common Mistakes:

• Not calculating half sum correctly
• Choosing subsets that don't sum to half
• Ignoring that partition may not exist