Partition Equal Subset Sum in DSA C

Mental Model

We want to split a list of numbers into two groups with the same total sum. We check if one group can reach half the total sum.

Analogy: Imagine you have a pile of coins and want to divide them into two piles with the same amount of money. You try to find if you can pick some coins to make exactly half the total value.

Array: [1, 5, 11, 5]
Total sum = 22
Target sum for one subset = 11
We try to find a subset that sums to 11.

Dry Run Walkthrough

Input: list: [1, 5, 11, 5]

Goal: Find if we can split the list into two subsets with equal sum (11 each).

Step 1: Calculate total sum = 1 + 5 + 11 + 5 = 22, target = 11

Total sum = 22, Target subset sum = 11

Why: We want to find a subset with sum 11 to confirm equal partition.

Step 2: Initialize boolean array dp[0..11] with dp[0] = true (sum 0 is always possible)

dp: [true, false, false, false, false, false, false, false, false, false, false, false]

Why: We start with sum 0 possible without any elements.

Step 3: Process number 1: update dp for sums including 1

dp: [true, true, false, false, false, false, false, false, false, false, false, false]

Why: Sum 1 is now possible by including the number 1.

Step 4: Process number 5: update dp for sums including 5

dp: [true, true, false, false, false, true, true, false, false, false, false, false]

Why: Sums 5 and 6 are possible by adding 5 to sums 0 and 1.

Step 5: Process number 11: update dp for sums including 11

dp: [true, true, false, false, false, true, true, false, false, false, false, true]

Why: Sum 11 is possible by adding 11 to sum 0.

Step 6: Process number 5: update dp for sums including 5 again

dp: [true, true, false, false, false, true, true, false, false, false, true, true]

Why: Sum 10 becomes possible by adding 5 to the previous sum 5.

Result:

dp[11] = true means subset with sum 11 exists.
Final answer: true (partition possible)

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool canPartition(int* nums, int numsSize) {
    int total = 0;
    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }
    if (total % 2 != 0) return false; // odd sum cannot be split equally
    int target = total / 2;
    bool dp[target + 1];
    memset(dp, false, sizeof(dp));
    dp[0] = true; // sum 0 is always possible

    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        for (int j = target; j >= num; j--) {
            if (dp[j - num]) {
                dp[j] = true; // update dp if sum j-num was possible
            }
        }
    }
    return dp[target];
}

int main() {
    int nums[] = {1, 5, 11, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    if (canPartition(nums, size)) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

if (total % 2 != 0) return false; // odd sum cannot be split equally

Check if total sum is odd; if yes, partition is impossible.

dp[0] = true; // sum 0 is always possible

Initialize dp array to mark sum 0 as achievable.

for (int i = 0; i < numsSize; i++) {

Iterate over each number to update possible sums.

for (int j = target; j >= num; j--) {

Traverse dp backwards to avoid using the same number multiple times.

if (dp[j - num]) { dp[j] = true; }

Mark sum j achievable if sum j-num was achievable before.

return dp[target];

Return if target sum is achievable, meaning partition possible.

Output

true

Complexity Analysis

Time: O(n * sum) because we check each number against all sums up to half the total

Space: O(sum) because we use a boolean array of size half the total sum

vs Alternative: Naive approach tries all subsets with exponential time; this DP approach is much faster and practical.

Edge Cases

Empty list

Returns true because empty subsets trivially partition equally

DSA C

if (total % 2 != 0) return false;

List with one element

Returns false because one element cannot be split into two equal subsets

DSA C

if (total % 2 != 0) return false;

List with all elements equal

Returns true if total sum is even, false otherwise

DSA C

if (total % 2 != 0) return false;

When to Use This Pattern

When you need to check if a list can be split into two equal sum parts, use the subset sum dynamic programming pattern to find if half the total sum is achievable.

Common Mistakes

Mistake: Iterating dp array forwards causing reuse of the same element multiple times
Fix: Iterate dp array backwards to avoid counting the same element more than once.

Mistake: Not checking if total sum is even before proceeding
Fix: Add a check to return false immediately if total sum is odd.

Summary

Checks if a list can be divided into two subsets with equal sums.

Use when you want to split data into two equal sum groups.

The key is to find if a subset sums to half the total sum using dynamic programming.

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