Partition Equal Subset Sum in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the total sum of the array.

DSA Javascript

const totalSum = nums[1]((a, b) => a + b, 0);

Drag options to blanks, or click blank then click option'

A.filter

B.map

C.reduce

D.forEach

Attempts:

3 left

💡 Hint

Common Mistakes

Using map instead of reduce, which returns an array instead of a single sum.

Using forEach which does not return a value.

The reduce method sums all elements in the array to get the total sum.

2fill in blank

medium

Complete the code to check if the total sum is odd and return false if so.

DSA Javascript

if (totalSum [1] 2 !== 0) return false;

Drag options to blanks, or click blank then click option'

A+

B*

C-

D%

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or - instead of modulo operator.

Using * which multiplies instead of checking remainder.

Using the modulo operator (%) checks if the sum is odd by checking remainder when divided by 2.

3fill in blank

hard

Fix the error in the loop to iterate through nums correctly.

DSA Javascript

for (let i = 0; i [1] nums.length; i++) {

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= causes index out of range error.

Using > or >= causes the loop to never run or run incorrectly.

The loop should run while i is less than nums.length to avoid going out of bounds.

4fill in blank

hard

Fill both blanks to update the dp array for subset sums.

DSA Javascript

for (let j = target; j >= [1]; j--) {
  dp[j] = dp[j] || dp[j [2] nums[i]];
}

Drag options to blanks, or click blank then click option'

Anums[i]

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction causes incorrect indexing.

Looping forwards causes incorrect dp updates.

We iterate backwards from target down to nums[i], and update dp[j] by checking dp[j - nums[i]].

5fill in blank

hard

Fill all three blanks to create the final function that returns if partition is possible.

DSA Javascript

function canPartition(nums) {
  const totalSum = nums[1]((a, b) => a + b, 0);
  if (totalSum [2] 2 !== 0) return false;
  const target = totalSum / 2;
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (let i = 0; i < nums.length; i++) {
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = dp[j] || dp[j [3] nums[i]];
    }
  }
  return dp[target];
}

Drag options to blanks, or click blank then click option'

A.reduce

B%

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using map instead of reduce for sum.

Using addition instead of modulo for odd check.

Using addition instead of subtraction in dp update.

The function sums the array with reduce, checks odd sum with %, and updates dp using subtraction.

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