Partition Equal Subset Sum in DSA C - 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

↓

If subset found

→Return True

No↓

Return False

Check if array can be split into two subsets with equal sum by verifying if a subset sums to half the total.

Execution Sample

DSA C

bool canPartition(int* nums, int numsSize) {
  int sum = 0;
  for (int i = 0; i < numsSize; i++) sum += nums[i];
  if (sum % 2 != 0) return false;
  int target = sum / 2;
  bool dp[target+1];
  memset(dp, 0, sizeof(dp));
  dp[0] = true;
  for (int i = 0; i < numsSize; i++) {
    for (int j = target; j >= nums[i]; j--) {
      dp[j] = dp[j] || dp[j - nums[i]];
    }
  }
  return dp[target];
}

Checks if array can be partitioned into two equal sum subsets using dynamic programming.

Execution Table

Step	Operation	Current Number	DP Array State	Action
1	Calculate total sum	-	-	Sum = 1+5+11+5 = 22
2	Check if sum even	22	-	22 is even, proceed
3	Set target	22	-	Target = 11
4	Initialize dp array	-	[true, false, false, false, false, false, false, false, false, false, false, false]	dp[0] = true
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]	Update dp for sums including 5
7	Process number 11	11	[true, true, false, false, false, true, true, false, false, false, false, true]	dp[11] = dp[11] || dp[0] = true
8	Process number 5	5	[true, true, false, false, false, true, true, false, false, false, true, true]	Update dp for sums including second 5
9	Check dp[target]	11	[true, true, false, false, false, true, true, false, false, false, true, true]	dp[11] is true, partition possible
10	Return result	-	-	Return true

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

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
sum	0	22	22	22	22	22	22	22	22
target	-	-	11	11	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	-

Key Moments - 3 Insights

Why do we check if the total sum is even 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 sum subsets.

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

Iterating backwards (Step 5-8) prevents using the same number multiple times in one iteration, ensuring each number is only counted once.

What does dp[j] = true mean at any point?

It means there exists a subset of numbers processed so far that sums exactly to j (see Steps 5-8).

Visual Quiz - 3 Questions

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

A undefined

B false

C true

D depends on previous steps

💡 Hint

Check the DP Array State column at Step 6 in execution_table

At which step does dp[target] become true for the first time?

A Step 7

B Step 5

C Step 8

D Step 9

💡 Hint

Look at the DP Array State and Action columns in execution_table

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

A Proceed with DP as usual

B Return false immediately

C Set target to 11

D Set target to 12

💡 Hint

Refer to Step 2 in execution_table where sum evenness is checked

Concept Snapshot

Partition Equal Subset Sum:
- Calculate total sum of array
- If sum is odd, return false
- Set target = sum / 2
- Use DP array dp[] where dp[j] = true means subset sums to j
- Iterate numbers, update dp 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 this sum is odd, partitioning is impossible, so we return false. Otherwise, we set a target as half the total sum. We then use a dynamic programming approach with a boolean array dp, where dp[j] indicates if a subset sums to j. We initialize dp[0] to true since sum zero is always possible with an empty subset. For each number in the array, we update dp backwards to avoid reusing the same number multiple times. If dp[target] becomes true, it means a subset with sum equal to target exists, so the array can be partitioned into two equal subsets. Otherwise, it cannot.