Partition DP

Overview

Partition problems ask whether a set can be split so the parts balance, and how many ways there are to hit a target sum. Both reduce to the subset-sum table from the knapsack lesson. Equal partition is the neat case: a set can be split into two equal halves only if its total is even and some subset sums to exactly half — so the feasibility question becomes one subset-sum query. Counting subsets that reach a target uses the same table with += instead of a boolean OR, and the same downward capacity sweep that keeps each element used at most once.

Why it matters

Balanced partitioning is load balancing: split jobs across two machines so they finish together, divide a bill fairly, distribute weight evenly across two containers. The counting variant answers "how many ways" questions in combinatorics and probability. And the parity shortcut — an odd total can never split evenly — is a good habit: cheap impossibility checks before expensive computation.

Core concepts

The parity gate. If the total is odd, no equal partition exists. Return early; this costs one pass and rules out half of all inputs.

Reduce to subset sum. With an even total S, ask whether any subset sums to S/2. If one does, the remaining elements necessarily sum to S/2 as well — so a single subset-sum query answers the partition question.

Feasibility table. dp[0] = 1 (the empty subset reaches zero), then for each element sweep the target downward: dp[s] |= dp[s - a[i]]. Downward is what enforces once-each use, exactly as in the 0/1 knapsack.

Counting table. Replace the OR with addition: dp[s] += dp[s - a[i]], still sweeping downward. dp[t] then holds the number of distinct subsets summing to t.

Zeros and negatives. An element equal to 0 doubles the count of every subset (include it or not) — correct, but surprising. Negative values break the amount-indexed table entirely; they need a shifted index range or a different formulation.

Complexity. O(n x target), pseudo-polynomial — fine for modest sums, expensive when the total is huge even if n is small.

Syntax notes

#include <stdlib.h>

int can_partition(const int *a, int n) {
    long long tot = 0;
    for (int i = 0; i < n; i++) tot += a[i];
    if (tot & 1) return 0;                       /* odd total -> impossible */
    int half = (int)(tot / 2);
    char *dp = calloc((size_t)half + 1, 1);
    if (!dp) return -1;
    dp[0] = 1;                                   /* empty subset reaches 0 */
    for (int i = 0; i < n; i++)
        for (int s = half; s >= a[i]; s--)       /* DOWNWARD: use each element once */
            if (dp[s - a[i]]) dp[s] = 1;
    int ok = dp[half];
    free(dp);
    return ok;
}

/* how many subsets sum to exactly t */
long long count_subsets(const int *a, int n, int t) {
    long long *dp = calloc((size_t)t + 1, sizeof *dp);
    if (!dp) return -1;
    dp[0] = 1;
    for (int i = 0; i < n; i++)
        for (int s = t; s >= a[i]; s--)
            dp[s] += dp[s - a[i]];
    long long r = dp[t];
    free(dp);
    return r;
}

Key points:

• Sum into long long before halving — the total can overflow int even when each element is small.
• Downward sweep = each element used at most once.
• dp[0] = 1 seeds both variants; calloc supplies the zeros everywhere else.

Lesson

Equal-sum partition asks whether a set splits into two equal halves — a subset-sum to total/2, feasible only when the total is even. Counting subsets with a given sum is the same table with addition instead of a boolean OR, tallying how many ways rather than whether.

Code examples

#include <stdio.h>
#include <stdlib.h>
static int can_partition(const int*a,int n){long long tot=0;for(int i=0;i<n;i++)tot+=a[i];if(tot&1)return 0;int half=tot/2;char*dp=calloc(half+1,1);dp[0]=1;for(int i=0;i<n;i++)for(int t=half;t>=a[i];t--)if(dp[t-a[i]])dp[t]=1;int r=dp[half];free(dp);return r;}
static long long count_subsets(const int*a,int n,int t){long long*dp=calloc(t+1,sizeof(long long));dp[0]=1;for(int i=0;i<n;i++)for(int s=t;s>=a[i];s--)dp[s]+=dp[s-a[i]];long long r=dp[t];free(dp);return r;}
int main(void){
    int a[]={1,5,11,5};
    printf("can {1,5,11,5} split into equal halves? %s\n", can_partition(a,4)?"yes":"no");
    int b[]={1,2,3,3};
    printf("subsets of {1,2,3,3} summing to 6 = %lld\n", count_subsets(b,4,6));
    return 0;
}

Line by line

Common mistakes

Not short-circuiting on an odd total; using OR when you meant to count.

Debugging tips

Compiler errors and warnings:

• warning: implicit conversion narrowing tot to int; cast explicitly after the parity check.
• -Wsign-compare at the calloc size; cast to size_t.

Runtime symptoms:

• Reports true for a set that cannot split. The sweep runs upward, letting an element be reused. Sweep downward.
• Always false. dp[0] = 1 is missing, so nothing is ever reachable.
• Crash or huge allocation. Negative elements make half or the index range meaningless — this formulation assumes non-negative values.
• Wrong for an odd total. The parity check is missing; tot / 2 silently truncates and you answer a different question.
• Counts overflow. Use long long, or the problem's modulus.

Technique: test {1,5,11,5} (true) and {1,2,3,5} (total 11, odd -> false immediately). The second confirms the parity gate fires before any allocation.

Memory safety

• Sum in a wider type. tot must be long long; summing many int values into an int can overflow (undefined behaviour) and produce a nonsense half.
• Validate before allocating. half derives from input data. A negative or absurdly large total turns (size_t)half + 1 into a wrapped or enormous allocation. Bound the input and check the result of calloc.
• Non-negative precondition. The table is indexed by sum, so negative elements would index below zero. Reject them at the boundary rather than relying on the loop condition.
• Zero-initialisation is required — both variants read entries before writing them.
• Free on every path, and read dp[half] into a local before freeing.

Real-world uses

Concrete uses: Splitting tasks between two workers so both finish at the same time. Balancing cargo across two holds. Dividing an expense fairly between two parties. In testing, generating balanced data splits. The counting variant answers combinatorial questions such as how many ways a score can be reached from a set of point values.

Professional best practices:

Beginner:

• Check parity before doing any real work.
• Remember the downward sweep; it is the same rule as the 0/1 knapsack.

Intermediate:

• State the non-negative precondition in the API and enforce it.
• For large totals, the pseudo-polynomial cost may be prohibitive — consider approximation or a different model.
• Use a bitset (one bit per reachable sum, shifted and ORed) for a large feasibility table; it is dramatically faster and reuses the bit-manipulation techniques from earlier in the curriculum.

Practice tasks

1. (Beginner) Equal partition. Implement int can_partition(const int *a, int n) with the parity gate. Example: {1,5,11,5} -> 1; {1,2,3,5} -> 0. Concepts: reduction to subset sum.

2. (Beginner) Count subsets. Implement long long count_subsets(const int *a, int n, int t). Example: {1,1,2,3}, t=3 -> 3. Concepts: counting instead of feasibility.

3. (Intermediate) Minimum difference. Find the smallest possible difference between the two parts when an equal split is impossible. Hint: find the largest reachable s <= tot/2; the answer is tot - 2*s. Concepts: using the whole reachability table.

4. (Intermediate) Bitset feasibility. Reimplement the feasibility test with a bitset, shifting by each element and ORing. Concepts: bit-parallel DP, reuse of the bitset lesson.

Summary

Partition problems reduce to subset sum. An equal split is possible only when the total is even and some subset reaches exactly half, so a cheap parity check comes first and one subset-sum query answers the rest. The table is seeded with dp[0] = 1 and swept downward for each element, which is what keeps every element used at most once; swapping the OR for += counts the subsets instead of merely testing feasibility. Sum into long long, enforce non-negative inputs because the table is indexed by sum, and remember the cost is pseudo-polynomial in the target.

Practice with these exercises

• Equal-sum partition
• Count subsets with a target sum