Partition Equal Subset Sum in DSA Javascript

Mental Model

We want to see if we can split a list of numbers into two groups with the same total. This means finding 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 picking some coins to see if their total matches half the pile.

Array: [1, 5, 11, 5]
Total sum: 22
Target subset sum: 11
Subset search: Can we find some numbers that add to 11?

[1] [5] [11] [5]
 ↑    ↑    ↑    ↑
Try combinations to reach 11

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 and target subset sum

Total sum = 1 + 5 + 11 + 5 = 22
Target subset sum = 22 / 2 = 11

Why: We want to find a subset that sums to half the total to split equally

Step 2: Start with empty subset sum 0, try adding 1

Possible sums: {0, 1}

Why: We can either take or skip 1, so sums are 0 or 1

Step 3: Add 5 to existing sums

Possible sums: {0, 1, 5, 6} (0+5=5, 1+5=6)

Why: Try adding 5 to all previous sums to get new sums

Step 4: Add 11 to existing sums

Possible sums: {0, 1, 5, 6, 11, 12, 16, 17} (adding 11 to each)

Why: Check if 11 can be formed by adding 11 to previous sums

Step 5: Add last 5 to existing sums

Possible sums: {0,1,5,6,11,12,16,17,5,6,10,11,16,17,21,22}
Simplified: {0,1,5,6,10,11,12,16,17,21,22}

Why: Add 5 to all sums to find new possible sums including 11

Step 6: Check if target sum 11 is in possible sums

11 is present in possible sums

Why: Finding 11 means we can split into two equal subsets

Result:

Possible sums include 11 -> Partition possible
Answer: true

Annotated Code

DSA Javascript

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

    for (const num of nums) {
      for (let s = target; s >= num; s--) {
        if (canSum[s - num]) {
          canSum[s] = true; // mark sum s achievable
        }
      }
    }
    return canSum[target];
  }
}

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

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

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

canSum[0] = true; // zero sum always possible

Initialize base case: sum zero is always achievable

for (const num of nums) {

Iterate over each number to update achievable sums

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

Traverse sums backward to avoid using updated sums in same iteration

if (canSum[s - num]) { canSum[s] = true; }

If sum s-num was achievable, sum s is now achievable by adding num

return canSum[target];

Return if target sum is achievable, meaning partition possible

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 store achievable sums up to half the total

vs Alternative: Naive approach tries all subsets with exponential time; this dynamic programming approach is much faster

Edge Cases

Empty list

Returns true because empty subsets trivially equal

DSA Javascript

if (totalSum % 2 !== 0) return false;

List with one element

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

DSA Javascript

if (totalSum % 2 !== 0) return false;

List with all zeros

Returns true because zero sum subsets are trivially equal

DSA Javascript

canSum[0] = true;

When to Use This Pattern

When asked if a list can be split into two equal sum parts, use the subset sum pattern to find if half the total sum can be formed.

Common Mistakes

Mistake: Iterating sums forward instead of backward causes using updated sums in the same iteration, leading to incorrect results.
Fix: Iterate sums backward from target to num to avoid reusing updated sums.

Mistake: Not checking if total sum is even before proceeding wastes time on impossible cases.
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 sum equal to half the total.

Use when you need to partition a set into two equal sum groups.

The key insight is that partitioning into equal sums 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 in a given array of positive integers?

easy

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

B. The maximum sum of any subset in the array

C. The minimum number of subsets needed to cover all elements

D. The sum of all elements in the array

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Compare options with problem definition

   Only Whether the array can be split into two subsets with equal sums matches this goal exactly. Other options describe different problems.

3. Final Answer:

   Whether 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: Look for splitting array into two equal sum parts [OK]

Common Mistakes:

• Confusing with finding max or min subset sums
• Thinking about number of subsets instead of sums
• Assuming sum of all elements is the answer

2. Which of the following JavaScript function signatures is correct to start solving the Partition Equal Subset Sum problem?

easy

A. function partition(nums, sum) {}

B. function partitionEqualSubsetSum() {}

C. function canPartition(nums) {}

D. function canPartition(nums, target) {}

Solution

1. Step 1: Identify typical function signature

   The problem usually takes one parameter: an array of numbers to check partitioning.

2. Step 2: Match options with typical usage

   function canPartition(nums) {} uses a clear, common name and one parameter for the array. Others add extra parameters or use less common names.

3. Final Answer:

   function canPartition(nums) {} -> Option C

4. Quick Check:

   Function with one array parameter = function canPartition(nums) {} [OK]

Hint: Use one array parameter named nums for input [OK]

Common Mistakes:

• Adding unnecessary parameters like target or sum
• Using unclear or inconsistent function names
• Missing the array parameter

3. What will be the output of the following code snippet?

function canPartition(nums) {
  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. false

B. true

C. undefined

D. TypeError

Solution

1. Step 1: Calculate total and check parity

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

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

   Target is 11. The dp array tracks sums possible. 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 sum found = true [OK]

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

Common Mistakes:

• Not checking if total sum is even
• Iterating dp array forward instead of backward
• Returning wrong dp index

4. Identify the bug in this code snippet for Partition Equal Subset Sum:

function canPartition(nums) {
  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

B. dp array size is incorrect

C. dp[0] should be false initially

D. Inner loop should run backward from target to num

Solution

1. Step 1: Check reduce usage

   Reduce without initial value works if array not empty, so no error here.

2. Step 2: Analyze inner loop direction

   Loop runs forward (j = num to target), which causes dp to use updated values in same iteration, leading to incorrect results. It should run backward to avoid reuse.

3. Final Answer:

   Inner loop should run backward from target to num -> Option D

4. Quick Check:

   Loop backward to avoid dp overwrite [OK]

Hint: Loop backward in dp to prevent using updated states [OK]

Common Mistakes:

• Running dp loop forward causing wrong results
• Assuming reduce needs initial value always
• Incorrect dp array initialization

5. Given the array [2, 2, 3, 5], which of the following modifications to the Partition Equal Subset Sum algorithm will correctly determine if the array can be partitioned into two equal sum subsets, considering the edge case where the total sum is odd?

hard

A. Add a check to return false immediately if the total sum is odd before running dp

B. Change dp array to track counts of subsets instead of booleans

C. Use recursion without memoization to explore all subsets

D. Ignore the total sum parity and run dp directly

Solution

1. Step 1: Calculate total sum and check parity

   Sum is 2+2+3+5 = 12, which is even, so partitioning is possible in theory.

2. Step 2: Importance of parity check before dp

   If sum is odd, no equal partition exists. Checking this early saves time and avoids unnecessary dp computation.

3. Step 3: Evaluate options for correctness

   Add a check to return false immediately if the total sum is odd before running dp correctly adds this check. Change dp array to track counts of subsets instead of booleans changes dp meaning incorrectly. Use recursion without memoization to explore all subsets is inefficient. Ignore the total sum parity and run dp directly ignores parity, causing wrong results.

4. Final Answer:

   Add a check to return false immediately if the total sum is odd before running dp -> Option A

5. Quick Check:

   Check sum parity before dp = Add a check to return false immediately if the total sum is odd before running dp [OK]

Hint: Always check if total sum is even before dp [OK]

Common Mistakes:

• Skipping sum parity check causing wrong answers
• Changing dp logic unnecessarily
• Using slow recursion without memoization