Partition Equal Subset Sum in DSA Typescript - Execution Trace

Concept Flow - Partition Equal Subset Sum

Calculate total sum of array

↓

Check if total sum is odd?

Yes→Return false: cannot partition

No↓

Set target = total sum / 2

↓

Use DP to check if subset sums to target

↓

If subset found

→Return true

No↓

Return false

We first find the total sum. If it's odd, partition is impossible. Otherwise, we try to find a subset with sum equal to half the total using dynamic programming.

Execution Sample

DSA Typescript

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];
}

This code checks if the array can be split into two subsets with equal sum by using a boolean DP array to track achievable sums.

Execution Table

Step	Operation	Current Number	DP Array State	Explanation
1	Calculate total sum	-	-	Sum of [1, 5, 11, 5] is 22
2	Check if sum is odd	22	-	22 is even, continue
3	Set target	22	-	Target sum is 11
4	Initialize dp array	-	[true, false, false, false, false, false, false, false, false, false, false, false]	dp[0] = true, others false
5	Process number 1	1	[true, true, false, false, false, false, false, false, false, false, false, false]	dp[1] = dp[1] || dp[0] = true
6	Process number 5	5	[true, true, false, false, false, true, true, false, false, false, false, false]	dp[5] and dp[6] updated
7	Process number 11	11	[true, true, false, false, false, true, true, false, false, false, false, true]	dp[11] updated to true
8	Process number 5	5	[true, true, false, false, false, true, true, false, false, false, true, true]	dp[10] updated to true
9	Check dp[target]	-	-	dp[11] is true, partition possible
10	Return result	-	true	Function returns true

💡 dp[target] is true, meaning a subset with sum 11 exists, so partition is possible

Variable Tracker

Variable	Start	After Step 5	After Step 6	After Step 7	After Step 8	Final
total	0	22	22	22	22	22
target	-	11	11	11	11	11
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	-
result	-	-	-	-	-	true

Key Moments - 3 Insights

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

Because if the total sum is odd (see Step 2 in execution_table), it's impossible to split the array into two equal subsets, so we return false immediately.

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

Iterating backwards (from target down to current number) prevents using the same number multiple times in one iteration, ensuring each number is only counted once (see Steps 5-8).

What does dp[j] = dp[j] || dp[j - num] mean in this context?

It means we mark sum j as achievable if it was already achievable or if sum j - num was achievable before adding current number num (see Steps 5-8).

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, what is the value of dp[5]?

A true

B false

C undefined

D null

💡 Hint

Check the DP Array State column at Step 6 in execution_table

At which step does dp[11] become true?

A Step 5

B Step 7

C Step 6

D Step 8

💡 Hint

Look at the DP Array State column in execution_table rows for dp[11]

If the total sum was 23 instead of 22, what would happen at Step 2?

A Continue to DP processing

B Set target to 11.5

C Return false immediately

D Throw an error

💡 Hint

Refer to the check for odd sum in Step 2 of execution_table

Concept Snapshot

Partition Equal Subset Sum:
- Calculate total sum of array
- If sum is odd, return false
- Set target = sum / 2
- Use boolean DP array dp of size target+1
- dp[0] = true (empty subset)
- For each number, update dp backwards
- Return dp[target] indicating if subset sum exists

Full Transcript

The Partition Equal Subset Sum problem checks if an array can be split into two subsets with equal sums. First, we sum all numbers. If the sum is odd, partitioning is impossible. If even, we set the target as half the sum. We use a boolean dynamic programming array dp where dp[j] means whether a subset sum j is achievable. We initialize dp[0] as true because sum zero is always possible with an empty subset. For each number, we update dp from the target down to the number, marking sums achievable by including that number. If dp[target] is true at the end, it means a subset with sum equal to half the total exists, so partitioning is possible. Otherwise, it is not.