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.

Practice

1. What does the Partition Equal Subset Sum problem ask you to find?

easy

A. If the array contains any duplicate elements

B. If the array is sorted in ascending order

C. If the array can be split into two subsets with equal sums

D. If the array contains only positive numbers

Solution

1. Step 1: Understand the problem statement

   The problem asks whether the given array can be divided into two parts where the sum of elements in both parts is the same.

2. Step 2: Identify the key requirement

   We need to check if there exists a subset whose sum is half of the total sum of the array.

3. Final Answer:

   If the array can be split into two subsets with equal sums -> Option C

4. Quick Check:

   Partition Equal Subset Sum = Split array equally [OK]

Hint: Check if total sum is even first to proceed [OK]

Common Mistakes:

• Thinking the problem is about sorting
• Checking for duplicates instead of sums
• Assuming all numbers must be positive

2. Which of the following is the correct way to declare a boolean array in C for dynamic programming in Partition Equal Subset Sum?

easy

A. boolean dp[sum+1];

B. int dp[sum+1];

C. bool dp = new bool[sum+1];

D. bool dp[sum+1];

Solution

1. Step 1: Identify correct C syntax for boolean arrays

   In C, bool is available via stdbool.h and arrays are declared as bool dp[size];.

2. Step 2: Check options for correctness

   bool dp[sum+1]; uses correct syntax. int dp[sum+1]; uses int, which is not boolean. bool dp = new bool[sum+1]; uses Java/C++ style dynamic allocation, not valid in C. boolean dp[sum+1]; uses 'boolean' which is not a C keyword.

3. Final Answer:

   bool dp[sum+1]; -> Option D

4. Quick Check:

   Use bool dp[size]; in C [OK]

Hint: Use stdbool.h and declare bool arrays with bool dp[size]; [OK]

Common Mistakes:

• Using 'boolean' instead of 'bool' in C
• Trying Java-style dynamic allocation in C
• Using int instead of bool for DP array

3. What will be the output of the following code snippet for array nums = {1, 5, 11, 5}?

#include 
#include 

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];
    for (int i = 0; i <= target; i++) dp[i] = false;
    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];
}

int main() {
    int nums[] = {1, 5, 11, 5};
    printf("%d\n", canPartition(nums, 4));
    return 0;
}

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Calculate total sum and check parity

   Sum = 1 + 5 + 11 + 5 = 22, which is even, so proceed.

2. Step 2: Use DP to check subset sum equals 11

   The DP array tracks sums achievable. The subset {11} and {1,5,5} both sum to 11, so dp[11] becomes true.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Subset sum exists = 1 [OK]

Hint: Check if half sum subset exists using DP [OK]

Common Mistakes:

• Not checking if total sum is even
• Incorrect DP initialization
• Looping forward instead of backward in DP

4. Identify the bug in this Partition Equal Subset Sum code snippet:

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];
    for (int i = 0; i < target; i++) dp[i] = false;
    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];
}

medium

A. Loop initializing dp should run till target inclusive

B. The sum calculation is incorrect

C. The inner loop should run forward, not backward

D. dp[0] should be false initially

Solution

1. Step 1: Check dp array initialization loop

   The loop runs from 0 to target-1, missing dp[target] initialization, which should be set to false.

2. Step 2: Correct the loop to include target index

   Change loop condition to i <= target to initialize all dp elements properly.

3. Final Answer:

   Loop initializing dp should run till target inclusive -> Option A

4. Quick Check:

   Initialize dp array fully including dp[target] [OK]

Hint: Initialize dp array fully including last index [OK]

Common Mistakes:

• Forgetting to initialize dp[target]
• Running inner loop forward causing wrong results
• Setting dp[0] to false instead of true

5. Given an array nums = {2, 2, 3, 5}, which of the following modifications will correctly determine if it can be partitioned into two subsets with equal sum using dynamic programming?

hard

A. Change the DP array to track counts of subsets instead of booleans

B. Use a 2D DP array where dp[i][j] means if sum j is possible with first i elements

C. Sort the array first and then apply the existing 1D DP approach

D. Only check if the largest element is less than half the total sum

Solution

1. Step 1: Understand limitations of 1D DP for some cases

   1D DP works but 2D DP is clearer and handles subset sums by tracking elements used.

2. Step 2: Use 2D DP where dp[i][j] shows if sum j is possible using first i elements

   This approach explicitly considers each element and sum, making it easier to debug and understand.

3. Step 3: Sorting or counting subsets is not necessary or sufficient

   Sorting doesn't affect subset sums. Counting subsets is more complex and not required for yes/no answer.

4. Final Answer:

   Use a 2D DP array where dp[i][j] means if sum j is possible with first i elements -> Option B

5. Quick Check:

   2D DP tracks sums per element [OK]

Hint: Use 2D DP for clear subset sum tracking [OK]

Common Mistakes:

• Sorting array expecting it to solve partition
• Counting subsets instead of checking existence
• Only checking largest element against half sum