Equal Subset Sum Partition (Split an Array into Two Equal-Sum Halves)

• Equal Subset Sum Partition reduces to a 0/1 Knapsack subset-sum feasibility check.
• If the total sum is odd, no equal split exists because two equal integers cannot produce an odd total.
• Otherwise, the target is total / 2, and the question becomes: does some subset sum to exactly that target?
• A boolean DP array dp[t] records whether target t is reachable using any combination of elements.
• Each number is processed once with a high-to-low sweep to enforce the 0/1 constraint.
• Time is **O(N * S/2) and space is O(S/2)** where S is the total sum.

What is the Equal Subset Sum Partition problem?

The Equal Subset Sum Partition problem asks whether a given set of positive integers can be divided into two subsets such that the sum of elements in each subset is equal. This is a classic decision problem that reduces directly to the 0/1 Knapsack pattern.

For example, given the set {1, 5, 11, 5} with total 22, we ask: can some subset sum to 11? Yes, {1, 5, 5} sums to 11 and {11} sums to 11, so the answer is true.

Why does the odd-total check matter?

If the total sum of all elements is odd, no partition into two equal-sum subsets can exist. Two equal integers always produce an even sum, so an odd total is an immediate false return. This short-circuit saves the entire DP computation in roughly half of all inputs.

package com.bank.core;

public class PartitionCheck {
    public static void main(String[] args) {
        int[] payouts = {3, 7, 5};
        int total = 0;
        for (int p : payouts) total += p;
        System.out.println("Total: " + total);
        System.out.println("Can partition: " + (total % 2 == 0));
        // Total: 15 (odd) -> Can partition: false
    }
}

Total: 15
Can partition: false

How does this reduce to 0/1 Knapsack?

Once the total is confirmed even, the target becomes total / 2. The problem then becomes: is there a subset of the given numbers that sums to exactly this target? This is the classic subset-sum feasibility problem, which is a special case of 0/1 Knapsack where the weight and value of each item are the same and the capacity is the target.

• Knapsack capacity = total / 2
• Each item's weight = its value = the number itself
• We ask: can we fill the knapsack to exactly full capacity?

How does the boolean DP array work?

We use a one-dimensional boolean array dp of size target + 1. The entry dp[t] means "some subset of the numbers processed so far sums to exactly t."

• Base case: dp[0] = true because the empty subset sums to zero.
• Transition: for each number num, sweep from target down to num and set dp[t] = dp[t] || dp[t - num].
• Answer: dp[target] after processing all numbers.

package com.bank.service;

import java.math.BigDecimal;

public class PayoutPartitionService {

    /**
     * Determines if payout amounts can be split into two equal-sum groups.
     * Used by the National Bank of India settlement desk to balance teller workloads.
     */
    public static boolean canPartition(int[] payouts) {
        int total = 0;
        for (int amount : payouts) {
            total += amount;
        }
        if (total % 2 != 0) {
            return false; // Odd total: impossible
        }
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // Empty subset sums to zero

        for (int amount : payouts) {
            // Sweep high to low so each amount is used at most once
            for (int t = target; t >= amount; t--) {
                dp[t] = dp[t] || dp[t - amount];
            }
            if (dp[target]) {
                return true; // Early exit
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] payouts = {15000, 5000, 11000, 5000, 14000};
        System.out.println("Payouts can be split equally: " + canPartition(payouts));
    }
}

javac -d out com/bank/service/PayoutPartitionService.java
java -cp out com.bank.service.PayoutPartitionService

Payouts can be split equally: true

Why does the high-to-low sweep matter?

The sweep from target down to num is the mechanism that enforces the 0/1 constraint: each number is used at most once. If we swept low to high, a single number could propagate through multiple targets in one pass, effectively allowing unlimited reuse (the unbounded knapsack variant).

// WRONG: low-to-high allows reuse of the same number
for (int t = amount; t <= target; t++) {
    dp[t] = dp[t] || dp[t - amount]; // amount may be counted multiple times
}

// CORRECT: high-to-low ensures each number is used once
for (int t = target; t >= amount; t--) {
    dp[t] = dp[t] || dp[t - amount]; // amount counted at most once
}

What are the edge cases?

Several edge cases deserve attention when implementing this solution.

• Single element: a single number cannot be split, so the answer is always false.
• All zeros: every element is zero, total is zero, dp[0] is already true, so the answer is true.
• Very large total: if the total exceeds the available memory for the DP array, you may need to check feasibility before allocating.
• Duplicate elements: duplicates are handled naturally because each element is processed independently.

package com.bank.core;

public class PartitionEdgeCases {
    public static void main(String[] args) {
        // Single element
        System.out.println(canPartition(new int[]{10000})); // false

        // All zeros
        System.out.println(canPartition(new int[]{0, 0, 0})); // true

        // Two equal elements
        System.out.println(canPartition(new int[]{5000, 5000})); // true
    }

    static boolean canPartition(int[] nums) {
        int total = 0;
        for (int n : nums) total += n;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int t = target; t >= num; t--) {
                dp[t] = dp[t] || dp[t - num];
            }
        }
        return dp[target];
    }
}

false
true
true

What is the time and space complexity?

The time complexity is **O(N * T) where N is the number of elements and T is total / 2. For each of the N elements, we iterate over T targets. The space complexity is O(T)** for the one-dimensional boolean array.

This is pseudo-polynomial: polynomial in the numeric value of the sum but exponential in the number of bits needed to represent it. For interview-sized inputs this is efficient, but for very large sums you would need to discuss approximation algorithms.

How is this different from Count of Subset Sum?

| Aspect | Equal Partition | Count of Subset Sum |
|---|---|---|
| Question | Can we split into two equal halves? | How many subsets sum to target? |
| DP array type | boolean[] | int[] or long[] |
| Update operation | dp[t] = dp[t] \|\| dp[t - num] | dp[t] += dp[t - num] |
| Base case | dp[0] = true | dp[0] = 1 |
| Result | dp[target] is true or false | dp[target] is the count |

Equal Partition is the feasibility version; Count of Subset Sum is the counting version. The sweep direction and 0/1 constraint are identical in both.

What should a senior engineer know?

A senior engineer should understand these deeper aspects of the problem.

• Bit-set optimization: replace the boolean array with a BitSet and use bitSet.or(bitSet.get(0, target - num + 1).shiftLeft(num)) style operations to process 64 targets per CPU word, significantly speeding up the inner loop.
• Early termination: exit as soon as dp[target] becomes true. This can save substantial work when a valid partition is found early.
• Overflow guard: if individual elements can be large, the total could overflow int. Use long for the sum computation.
• Reconstruction: to actually find the partition (not just decide feasibility), keep a parent array recording which number caused each target to become reachable, then backtrack from the target.

package com.bank.service;

import java.util.BitSet;

public class PartitionBitSet {
    public static boolean canPartition(int[] nums) {
        int total = 0;
        for (int n : nums) total += n;
        if (total % 2 != 0) return false;
        int target = total / 2;
        BitSet reachable = new BitSet(target + 1);
        reachable.set(0);
        for (int num : nums) {
            // Process high to low by shifting and OR-ing
            for (int t = target; t >= num; t--) {
                if (reachable.get(t - num)) {
                    reachable.set(t);
                }
            }
            if (reachable.get(target)) return true;
        }
        return reachable.get(target);
    }
}

What are common interview follow-up questions?

Interviewers often extend this problem in several directions.

• Print the two subsets: requires backtracking through the DP table to recover which elements were chosen.
• Minimize the difference: instead of requiring exactly equal halves, find the partition that minimizes the absolute difference between the two subset sums.
• Three-way partition: can the array be split into three subsets of equal sum? This requires a two-dimensional DP.
• With negative numbers: the standard approach assumes positive numbers. Negatives require shifting the DP range or using a hash map.