Minimum sum partition | Solved using Tabulation in Python

Given an array arr[]  containing non-negative integers, the task is to divide it into two sets set1 and set2 such that the absolute difference between their sums is minimum and find the minimum difference.

Here’s the [Problem Link] to begin with.

Examples:

Input: arr[] = [1, 6, 11, 5]
Output: 1
Explanation: 
Subset1 = {1, 5, 6}, sum of Subset1 = 12 
Subset2 = {11}, sum of Subset2 = 11 
Hence, minimum difference is 1.  

Input: arr[] = [1, 4]
Output: 3
Explanation: 
Subset1 = {1}, sum of Subset1 = 1
Subset2 = {4}, sum of Subset2 = 4
Hence, minimum difference is 3.

Input: arr[] = [1]
Output: 1
Explanation: 
Subset1 = {1}, sum of Subset1 = 1
Subset2 = {}, sum of Subset2 = 0
Hence, minimum difference is 1.

Constraints:
1 ≤ arr.size()*|sum of array elements| ≤ 10⁵
1 <= arr[i] <= 10⁵

Tabulation (Bottom-Up DP)

Intuition and Approach

• Build a boolean DP table dp[n][total+1], where dp[i][t] is True if a subset of nums[0..i] can achieve sum t.
• Initialize:
  • dp[i] = True for all i (sum 0 achievable with empty subset).
  • dp[nums] = True if within bounds.
• Transition for each index and target:
  • pick = dp[i−1][t − nums[i]] if nums[i] ≤ t else False
  • not_pick = dp[i−1][t]
  • dp[i][t] = pick or not_pick
• After filling, iterate over all achievable s1 and compute min |total − 2*s1|.

Code Implementation

class Solution:
    def minDifference(self, nums):
        n = len(nums)
        total = sum(nums)
        # dp[i][t] -> can we make sum t using elements up to index i?
        dp = [[False for _ in range(total + 1)] for _ in range(n)]
        # Base: sum 0 is always achievable (empty subset)
        for index in range(n):
            dp[index] = True
        # Seed with the first element if within range
        if nums <= total:
            dp[nums] = True
        # Fill DP table
        for index in range(1, n):
            for target in range(0, total + 1):
                if nums[index] > target:
                    pick = False
                else:
                    pick = dp[index - 1][target - nums[index]]
                not_pick = dp[index - 1][target]
                dp[index][target] = pick or not_pick
        # Sweep all achievable sums s1 to minimize |total - 2*s1|
        min_diff = float("inf")
        for s1 in range(0, total + 1):
            if dp[n - 1][s1] == True:
                s2 = total - s1
                min_diff = min(min_diff, abs(s1 - s2))
        return min_diff

How It Works

• The DP table captures all reachable subset sums using the first i elements.
• Once populated, every True at dp[n−1][s1] indicates a candidate split S1/S2.
• The best split is the one minimizing |total − 2·s1|.

Time and Space Complexity

• Time: O(n × total) – standard subset-sum DP.
• Space: O(n × total) – full table.

Tabulation (Space Optimization)

Intuition and Approach

• Each row depends only on the previous row, so we can reduce memory to two 1D arrays (prev and curr).
• The transition remains the same; we just roll arrays per element.
• After processing all elements, prev[t] tells if sum t is achievable.

Code Implementation

class Solution:
    def minDifference(self, nums):
        n = len(nums)
        total = sum(nums)
        # prev[t] -> achievable sum t using elements up to previous index
        prev = [False for _ in range(total + 1)]
        prev[0] = True  # sum 0 is always achievable
        if nums <= total:
            prev[nums] = True  # seed with first element
        # Build achievable sums iteratively
        for index in range(1, n):
            curr = [False for _ in range(total + 1)]
            for target in range(0, total + 1):
                if nums[index] > target:
                    pick = False
                else:
                    pick = prev[target - nums[index]]
                not_pick = prev[target]
                curr[target] = pick or not_pick
            prev = curr  # roll the arrays
        # Scan all achievable s1 to minimize |total - 2*s1|
        min_diff = float("inf")
        for s1 in range(0, total + 1):
            if prev[s1] == True:
                s2 = total - s1
                min_diff = min(min_diff, abs(s1 - s2))
        return min_diff

How It Works

• The rolling arrays preserve correctness while cutting space from O(n×total) to O(total).
• The final pass over achievable sums finds the minimal difference.

Time and Space Complexity

• Time: O(n × total) – same as full DP.
• Space: O(total) – memory-optimized with rolling arrays.

Practical Tips

• You can restrict the final sweep to s1 in [0..total//2] since differences mirror around half the total, but the provided code correctly checks all sums for simplicity.
• This DP pattern is a direct extension of Subset Sum and closely related to Partition Equal Subset Sum; all share the same pick/not-pick transitions.

Conclusion

The Minimum Sum Partition problem reduces to computing all achievable subset sums and selecting the one closest to half the total. The tabulation approach is clear and robust, while the space-optimized version is preferred for tight memory limits. Both run in O(n × total) time, making them practical for common constraints.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.