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.