Partition Equal Subset Sum, in depth: the S/2 reduction, the one-row DP, recovering the split, minimum difference and k-way partition

From two groups to one target

Let S be the sum of the numbers. If two groups have equal totals, each total is S/2. So the question becomes: is there a subset whose sum is exactly S/2? Whatever is left over automatically sums to S/2 as well. That turns a problem about two groups into a problem about one target, which is subset sum, a member of the 0/1 knapsack family covered in the knapsack article.

Three checks dispose of many inputs before any table is built:

• Odd total. If S is odd, S/2 is not an integer, so the answer is no. For [1, 2, 3, 5], S = 11 and we stop.
• One item too large. If the largest number exceeds S/2, it cannot fit in either group. For [1, 2, 3, 10], S = 16, the target is 8, and 10 is larger, so the answer is no.
• Trivial sizes. One item can never be split; an empty list splits into two empty groups, which most problem statements exclude.

The recurrence and the one-row table

Define reach[s] as true when some subset of the items processed so far sums to s. Before any items, only the empty subset exists, so reach[0] is true and everything else false. When item x arrives, a sum s becomes reachable if it was already reachable without x, or if s minus x was reachable and we add x. That is the whole recurrence. The general recipe of choosing a state, a recurrence and an order is laid out in dynamic programming from first principles.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    if max(nums, default=0) > target:
        return False
    reach = [False] * (target + 1)
    reach[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):      # downwards: each item used at most once
            if reach[s - x]:
                reach[s] = True
        if reach[target]:
            return True                          # early exit
    return reach[target]

The inner loop runs from the target down to x, and the direction is the entire difference between 0/1 and unbounded use. Going downwards, when we read reach[s - x] it still holds the value from before this item, because smaller indices have not been updated yet. Going upwards, reach[s - x] might have just been set by this same item, so x could be counted twice. With one item 3, a table over sums 0 to 6 and an upward loop, reach[3] becomes true and then reach[6] reads it and becomes true too, as if we had two 3s. The upward loop is correct for coin change, where reuse is allowed, which is why the coin change article loops the other way.

Worked example

Take nums = [3, 1, 5, 9, 12]. The total is 30, which is even, so the target is 15, and the largest item, 12, does not exceed it. Track the reachable sums after each item.

After item 9, sum 15 is reachable (6 + 9, where 6 was 1 + 5), so the function returns true without looking at 12. The answer is yes: {1, 5, 9} and {3, 12} both total 15. Notice that sums 2, 7 and 11 never appear; with these numbers no subset hits them. The table holds target + 1 booleans, here 16, regardless of how many items there are.

Recovering the actual split

Interviewers often stop at true or false, but a load balancer needs the actual groups. The one-row boolean table cannot provide them: after the loop, reach[15] is true, but nothing records which item made it true, and later items have overwritten the history. You need extra information. The classic option is the full two-dimensional table, reach[i][s] for the first i items, which costs n times (S/2 + 1) booleans and lets you walk back from the last row. A cheaper option keeps one integer per sum: the index of the item that first made that sum reachable.

def partition_sets(nums):
    """Return (left, right) index lists with equal sums, or None."""
    total = sum(nums)
    if total % 2:
        return None
    target = total // 2
    first = [-1] * (target + 1)         # item index that first reached s; -1 = unreached
    first[0] = len(nums)                # sentinel: reachable with no items
    for i, x in enumerate(nums):
        for s in range(target, x - 1, -1):
            if first[s] == -1 and first[s - x] != -1:
                first[s] = i
    if first[target] == -1:
        return None
    left, s = [], target
    while s:
        i = first[s]
        left.append(i)
        s -= nums[i]
    chosen = set(left)
    return sorted(left), [i for i in range(len(nums)) if i not in chosen]

Why does the walk back never reuse an item? When item i first sets first[s], the sum s - x was reached by an earlier item, because the downward loop has not yet touched smaller sums for item i. So each step back moves to a strictly smaller item index, and the indices collected are distinct. For the worked example, first ends as [5, 1, -1, 0, 1, 2, 2, -1, 2, 2, 3, -1, 3, 3, 3, 3]. Starting at 15: first[15] = 3 (the 9), leaving 6; first[6] = 2 (the 5), leaving 1; first[1] = 1 (the 1), leaving 0. The function returns left indices [1, 2, 3] and right indices [0, 4], that is {1, 5, 9} and {3, 12}. On the classic input [1, 5, 11, 5] it returns [2] and [0, 1, 3]: {11} against {1, 5, 5}. Memory is target + 1 integers instead of n times that many booleans.

Complexity: weakly NP-complete

The table approach runs in O(n times S/2) time and O(S/2) space. That looks polynomial but is not, in the formal sense, because S is a number, not the size of the input: each extra bit per value doubles S, so S can be exponential in the input length. Partition is NP-complete, but only weakly NP-complete: it has this pseudo-polynomial algorithm, which is fast whenever the values are small. With 200 numbers each at most 100, S/2 is at most 10,000 and the table needs about two million updates, which is instant. With 40 numbers around 10^12, the table is hopeless.

Two techniques extend the range, and each is covered in depth elsewhere on the site. A bitset packs the reach array into machine words so one shift-and-OR processes 64 sums at once; in Python an arbitrary-precision integer does this for free, as shown in subset sum counting. When values are huge but n is at most about 40, meet-in-the-middle enumerates the sums of each half, sorts one list, and searches it, in roughly 2 to the n/2 time, as described in the knapsack article.

Minimum difference and the differencing heuristic

Often an exact split is impossible and you want the closest one: minimise the difference between the two totals. The same table answers it. Find the largest reachable sum that does not exceed S/2; call it best. The difference is S minus twice best.

def min_difference(nums):
    total = sum(nums)
    half = total // 2
    reach = 1                          # bit s set means sum s is reachable
    for x in nums:
        reach |= reach << x
    reach &= (1 << (half + 1)) - 1     # keep sums 0..half
    best = reach.bit_length() - 1
    return total - 2 * best

For [1, 2, 3, 10] the total is 16 and the best sum not above 8 is 6, so the answer is 4: {1, 2, 3} against {10}. A popular alternative for large values is the Karmarkar-Karp differencing heuristic: repeatedly remove the two largest numbers and insert their difference, and the last number left is the difference achieved. It is fast and often very good, but it is a heuristic, not an exact method. On [8, 7, 6, 5, 4] it takes 8 and 7 to get 1, then 6 and 5 to get 1, then 4 and 1 to get 3, then 3 and 1 to get 2, and reports 2. The exact table finds 0, because {8, 7} and {6, 5, 4} both total 15. Use differencing when the values are too large for the table and an approximate answer is acceptable; use the table whenever S/2 is small enough to allocate.

Partition into k equal groups

Splitting into k groups of equal sum is a different beast. For any fixed k a pseudo-polynomial DP over the first k - 1 group totals still exists, but its table grows like S to the power k - 1. When k is part of the input the problem is strongly NP-complete, because 3-partition reduces to it, so no pseudo-polynomial algorithm exists unless P equals NP. For small n, a bitmask DP over which items are used works well. Sort descending so large items fail fast, and track how full the current group is; when it reaches the side length, the next item starts a new group.

from functools import lru_cache

def can_partition_k(nums, k):
    total = sum(nums)
    if total == 0:
        return True                    # empty or all zeros
    if total % k:
        return False
    side = total // k
    nums = sorted(nums, reverse=True)
    if nums[0] > side:
        return False
    n = len(nums)

    @lru_cache(maxsize=None)
    def solve(mask, fill):
        if mask == (1 << n) - 1:
            return True
        for i in range(n):
            if mask >> i & 1 or fill + nums[i] > side:
                continue
            if solve(mask | 1 << i, (fill + nums[i]) % side):
                return True
        return False

    return solve(0, 0)

The fill value is determined by the mask, so the state space is at most 2 to the n, and each state tries n items: O(n times 2 to the n). On [4, 3, 2, 3, 5, 2, 1] with k = 4, each group must total 5, and the function returns true ({5}, {4, 1}, {3, 2}, {3, 2}). On [1, 2, 3, 4] with k = 3 the total 10 is not divisible by 3, so it returns false immediately. This is practical up to about 20 items.

Failure modes

• Upward inner loop. Items get reused: run the bare loop upwards with one item 3 over sums 0 to 6 and it marks 6 as reachable. Always loop down for 0/1.
• Forgetting the parity check. Integer division silently floors an odd total and the code answers a different question.
• Reconstructing from the boolean row. It has no history; keep first-item indices or the 2-D table.
• Negative numbers or zeros. The table assumes non-negative values; negatives need an offset and a wider range, and zeros can go in either group.
• Huge values. A target in the billions allocates gigabytes; check S/2 against a memory budget and switch to meet-in-the-middle or a heuristic.
• Trusting a heuristic as exact. Karmarkar-Karp and greedy largest-first can miss perfect splits, as the [8, 7, 6, 5, 4] example shows.

Testing it

Test against brute force. For random lists of up to 15 small integers, enumerate all 2 to the n subsets, compute the true answer, and compare with the DP. Check that every reconstructed split has disjoint indices, covers every item, and has equal sums. Add the edge cases explicitly: odd totals, a single dominant item, all equal values, many duplicates and lists containing zeros. A property-based testing library such as Hypothesis automates the random part and shrinks failures to a minimal example.

What to do next

1. Implement can_partition with the parity check, the max check, the downward loop and the early exit.
2. Trace it by hand on [3, 1, 5, 9, 12] and confirm the reachable sets match the table above.
3. Add first-item tracking and return the two groups; verify them with a checker, not by eye.
4. Write a brute-force comparator and run a few thousand random cases.
5. Implement min_difference and compare it with Karmarkar-Karp on [8, 7, 6, 5, 4].
6. Before using the table in production, compute S/2 and reject inputs whose table would exceed your memory budget.
7. Read the subset sum counting and knapsack articles for bitsets and meet-in-the-middle.