Partition Equal Subset Sum in DSA Javascript - Execution Trace

Concept Flow - Partition Equal Subset Sum

Calculate total sum of array

↓

Is total sum even?

No→Return false: cannot partition

Yes↓

Set target = total sum / 2

↓

Use DP to check if subset sums to target

↓

Return true if subset found, else false

We first check if the total sum is even. If yes, we try to find a subset with sum equal to half the total using dynamic programming.

Execution Sample

DSA Javascript

const nums = [1, 5, 11, 5];
const total = nums.reduce((a,b) => a+b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
// DP array to track sums
const dp = 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];

This code checks if the array can be split into two subsets with equal sum using a bottom-up dynamic programming approach.

Execution Table

Step	Operation	Current Number	DP Array State	Explanation
0	Initialize dp array	-	[true, false, false, false, false, false, false, false, false, false, false, false]	dp[0] = true means sum 0 is always possible
1	Process number 1	1	[true, true, false, false, false, false, false, false, false, false, false, false]	Sum 1 is now possible (0 + 1)
2	Process number 5	5	[true, true, false, false, false, true, true, false, false, false, false, false]	Sum 5 and 6 possible (0+5, 1+5)
3	Process number 11	11	[true, true, false, false, false, true, true, false, false, false, false, true]	Sum 11 possible (0+11)
4	Process number 5	5	[true, true, false, false, false, true, true, false, false, false, true, true]	Sum 10 possible (5+5) and others updated
5	Check dp[target]	-	dp[11] = true	Target sum 11 found as true, partition possible

💡 DP array shows dp[target] = true, so partition into equal subsets is possible

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
dp	[true, false, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, true]	[true, true, false, false, false, true, true, false, false, false, true, true]	[true, true, false, false, false, true, true, false, false, false, true, true]
current number	-	1	5	11	5	-
target	11	11	11	11	11	11

Key Moments - 3 Insights

Why do we check if the total sum is even before proceeding?

Because if the total sum is odd, it is impossible to split the array into two equal sum subsets. This is shown in execution_table step 0 where we decide to return false if sum is odd.

Why do we iterate backwards in the inner loop when updating dp array?

Iterating backwards prevents using the same number multiple times in one iteration. This ensures each number is only counted once per subset, as seen in execution_table steps 2-4.

What does dp[j] = true mean in the dp array?

It means there exists a subset of numbers processed so far that sums exactly to j. For example, dp[5] = true after processing number 5 means sum 5 is achievable.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what sums are possible after processing number 5?

A Sum 0, 1, 5, and 6

B Sum 5 and 11

C Only sum 5

D Sum 1 and 6 only

💡 Hint

Check the dp array state column at step 2 in execution_table

At which step does the dp array first show that sum 11 is possible?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the dp array state in execution_table rows and find when dp[11] becomes true

If the total sum was 25 instead of 22, what would happen at the initial check?

A We proceed with target = 12.5

B We return false immediately

C We try to find subset sum 25

D We ignore the sum and continue

💡 Hint

Refer to concept_flow where total sum odd check leads to immediate false

Concept Snapshot

Partition Equal Subset Sum:
- Check if total sum is even
- Target = total sum / 2
- Use DP array dp of size target+1
- dp[0] = true (sum 0 always possible)
- For each num, update dp[j] = dp[j] || dp[j-num] backwards
- Return dp[target] as result

Full Transcript

The Partition Equal Subset Sum problem checks if an array can be split into two subsets with equal sums. First, we calculate the total sum of the array. If the sum is odd, we return false immediately because equal partition is impossible. If even, we set the target as half the total sum. We use a dynamic programming approach with a boolean array dp where dp[j] indicates if a subset sum j is possible. We initialize dp[0] as true. For each number in the array, we update dp backwards to avoid reuse of the same number in one iteration. After processing all numbers, if dp[target] is true, it means a subset with sum equal to target exists, so partition is possible. The execution table shows step-by-step how dp array changes with each number processed. Key moments clarify why sum parity check is needed, why backward iteration is used, and what dp array values mean. The visual quiz tests understanding of dp array states and initial checks.

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