Partition equal subset sum

Decide whether an array can be split into two groups with equal totals. A subset-sum problem in disguise.

The idea

Two equal halves are only possible if the total is even, and then each half must equal total / 2. So the question becomes: can some subset of the array add up to exactly that target? dp[i, t] tracks whether sum t is reachable using the first i numbers.

Code

public static bool CanPartition(int[] a) {
    int total = a.Sum();
    if (total % 2 != 0) return false;
    int target = total / 2;
    var dp = new bool[a.Length + 1, target + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = true;
    for (int i = 1; i <= a.Length; i++)
        for (int t = 1; t <= target; t++) {
            dp[i, t] = dp[i - 1, t];
            if (a[i - 1] <= t && dp[i - 1, t - a[i - 1]])
                dp[i, t] = true;
        }
    return dp[a.Length, target];
}

Tips

• If the total is odd, stop immediately: no equal split can exist.
• This is exactly the 0/1 knapsack shape with every value treated as its own weight.

In the .NET library

The odd-total check is a cheap O(n) guard that avoids building a table that can never succeed. Always check it before running the O(n × sum) table fill.