Minimum Sum Partition: DP Table, Worked Example, and Code

Given an integer array, the minimum sum partition problem asks you to split it into two subsets so that the absolute difference between their sums is as small as possible.

The problem appears in placement coding tests at service-tier and product companies alike. Greedy strategies fail here. The partition problem is NP-complete in the general case, but dynamic programming solves it in pseudo-polynomial time proportional to the input sum.

What the Problem Asks

Formally: divide a set of non-negative integers into two disjoint subsets S1 and S2 such that the absolute difference |sum(S1) - sum(S2)| is minimised. Every element belongs to exactly one subset.

Sample input and output for the canonical example:

• Input array: [14, 25, 78, 96]
• One optimal split: S1 = {96, 14} with sum 110, S2 = {78, 25} with sum 103
• Minimum difference: |110 - 103| = 7

This differs from the equal-sum partition decision problem, which asks only whether difference 0 is achievable. Minimum sum partition always returns a numeric answer, which may or may not be 0.

The DP Approach

A greedy strategy (sort descending, assign each element to the smaller-sum half) does not guarantee the optimum. It ignores future elements that could produce a better split. The problem needs global knowledge of which subset sums are reachable.

The core insight reduces the search. If one subset has sum j, the other has sum S - j, and the difference is |S - 2j|. Minimising the difference is the same as finding the largest j that is <= S // 2 and is reachable as a subset sum.

Define dp[i][j] as True when some subset of the first i elements sums to exactly j. The table has dimensions (n+1) by (total+1).

Base case: dp[i][0] is True for all i from 0 to n. The empty subset always sums to 0.

Transition: for each element arr[i-1] and each target sum j:

• Exclude the element: dp[i-1][j] is unchanged.
• Include the element: dp[i-1][j - arr[i-1]] if j >= arr[i-1].
• dp[i][j] is True if either branch is True.

After filling the table, scan the last row from j = S // 2 down to 0. The first j where dp[n][j] is True is the largest reachable subset sum at or below half the total. Return S - 2 * j.

Tracing Through the Example

Array: [14, 25, 78, 96], total sum S = 213, half = 213 // 2 = 106.

Rather than drawing the full 5 by 214 table, the answer comes from one question: which values of j from 0 to 106 are reachable as subset sums?

Reachable sums at or below 106:

• Single elements within range: 14, 25, 78 (96 exceeds 106)
• Pairs within range: 14+25=39, 14+78=92, 25+78=103
• Pairs that exceed 106: 14+96=110, 25+96=121
• Triples that exceed 106: 14+25+78=117

Scanning from 106 downward: 106, 105, and 104 are all unreachable. The first hit is j = 103 (the pair {25, 78}).

Answer: 213 - 2 * 103 = 213 - 206 = 7.

The full DP table would confirm dp[4][103] is True and dp[4][104] through dp[4][106] are all False.

Python Implementation

The code below builds the full 2D table for clarity.

def min_sum_partition(arr):
    n = len(arr)
    total = sum(arr)
    half = total // 2

    # dp[i][j] = True if a subset of arr[0..i-1] sums to j
    dp = [[False] * (total + 1) for _ in range(n + 1)]

    # Base case: empty subset sums to 0
    for i in range(n + 1):
        dp[i][0] = True

    # Fill the table
    for i in range(1, n + 1):
        for j in range(1, total + 1):
            dp[i][j] = dp[i - 1][j]          # exclude arr[i-1]
            if j >= arr[i - 1]:
                dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i - 1]]

    # Find the largest reachable j at or below half
    for j in range(half, -1, -1):
        if dp[n][j]:
            return total - 2 * j

    return total  # degenerate: all elements in one subset

# Example
print(min_sum_partition([14, 25, 78, 96]))  # Output: 7

The space-optimised 1D variant uses a single array and traverses right to left to prevent double-counting within a single element:

def min_sum_partition_1d(arr):
    total = sum(arr)
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True

    for num in arr:
        for j in range(half, num - 1, -1):
            if dp[j - num]:
                dp[j] = True

    for j in range(half, -1, -1):
        if dp[j]:
            return total - 2 * j

    return total

print(min_sum_partition_1d([14, 25, 78, 96]))  # Output: 7

Both functions produce the same result. The 1D version is preferred in memory-constrained settings.

Time and Space Complexity

Two nested loops give the 2D approach O(n times S) time: the outer loop runs over n elements, the inner over sums from 0 to S. The table requires O(n times S) space. For large inputs this grows: 100 elements with a total sum of 10000 generates a table of 101 by 10001 entries.

The 1D optimisation reduces space complexity to O(S) by collapsing the row dimension. Time remains O(n times S). The right-to-left traversal is the same 0/1 knapsack technique used across subset-selection problems. The GeeksforGeeks walkthrough of minimum sum partition covers both the 2D and 1D formulations with C++ examples.

Other array problems that use a similar table-over-a-linear-sequence structure include finding symmetric pairs in an array (hash map as an implicit lookup table) and finding the equilibrium index (prefix-sum array as an implicit DP state). The underlying pattern is the same: encode reachable states in a data structure, then query that structure in a final pass.

The “scan from S/2 downward” step in partition DP is the same structure used in resource allocation and scheduling optimisation in production ML pipelines, where a budget constraint replaces S/2 and the goal is the closest feasible assignment. TinkerLLM at ₹299 is where that first applied experiment lives, moving from reading DP solutions to writing code that solves a real constraint-satisfaction problem in a deployed AI context.