Partition Equal Subset Sum in DSA Javascript - Build from Scratch

Partition Equal Subset Sum

📖 Scenario: You have a list of numbers representing weights of items. You want to check if you can split these items into two groups with the same total weight.

🎯 Goal: Build a program that checks if the list of numbers can be divided into two subsets with equal sum.

📋 What You'll Learn

Create an array called nums with the exact values [1, 5, 11, 5].

Create a variable called target that holds half of the total sum of nums.

Write a function called canPartition that uses a dynamic programming approach to check if a subset with sum equal to target exists.

Print the result of calling canPartition(nums, target).

💡 Why This Matters

🌍 Real World

Partitioning items into two groups with equal weight is useful in load balancing, resource allocation, and dividing tasks evenly.

💼 Career

Understanding subset sum problems and dynamic programming is important for software engineers working on optimization, algorithms, and coding interviews.

1

Create the array of numbers

Create an array called nums with the exact values [1, 5, 11, 5].

DSA Javascript

# Create the array nums with values [1, 5, 11, 5]
// Your code here

Hint

Use const nums = [1, 5, 11, 5]; to create the array.

2

Calculate the target sum

Create a variable called target that holds half of the total sum of the array nums. Use nums.reduce((a, b) => a + b, 0) to find the total sum.

DSA Javascript

const nums = [1, 5, 11, 5];
// Create variable target as half of sum of nums
// Your code here

Hint

Calculate sum with nums.reduce((a, b) => a + b, 0) and divide by 2.

3

Write the function to check partition

Write a function called canPartition that takes nums and target as parameters. Use a boolean array dp of length target + 1 initialized with false except dp[0] = true. For each number in nums, update dp from right to left to mark sums that can be formed. Return dp[target].

DSA Javascript

const nums = [1, 5, 11, 5];
const target = nums.reduce((a, b) => a + b, 0) / 2;
// Write function canPartition(nums, target) using dp array
// Your code here

Hint

Use a boolean array dp to track sums possible. Update it backwards for each number.

4

Print the result

Print the result of calling canPartition(nums, target) using console.log.

DSA Javascript

const nums = [1, 5, 11, 5];
const target = nums.reduce((a, b) => a + b, 0) / 2;

function canPartition(nums, target) {
    if (!Number.isInteger(target)) return false;
    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];
}
// Print the result of canPartition(nums, target)
// Your code here

Hint

Use console.log(canPartition(nums, target)); to print the result.

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