1. Introduction

The Minimum Sum Partition Problem is a classic optimization problem which aims to partition a set into two subsets such that the difference of their sum is minimized. Given an array of integers, we are to split it into two subsets such that the absolute difference between their sums is minimized. This problem is a variant of the subset-sum problem and can be solved using dynamic programming.

2. Program Steps

1. Create a boolean DP table where dp[i][j] will be true if array elements from 0 to i have a subset with sum equal to j.

2. Compute the sum of the array and initialize the answer as the sum.

3. Compute the subset sums for each possible subset and update the answer by finding the subset with minimum difference in sum.

3. Code Program

public class MinPartition {

    public static int findMinSumPartition(int[] arr) {
        int n = arr.length;

        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];

        boolean[][] dp = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; i++)
            dp[i][0] = true;

        for (int i = 1; i <= sum; i++)
            dp[0][i] = false;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j];

                if (arr[i - 1] <= j)
                    dp[i][j] |= dp[i - 1][j - arr[i - 1]];
            }
        }

        int diff = Integer.MAX_VALUE;

        for (int j = sum / 2; j >= 0; j--) {
            if (dp[n][j] == true) {
                diff = sum - 2 * j;
                break;
            }
        }
        return diff;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 9};
        System.out.println("The minimum difference is: " + findMinSumPartition(arr));
    }
}

Output:

The minimum difference is: 3

4. Step By Step Explanation

1. Firstly, we calculate the sum of all array elements.

2. We create a 2D boolean DP table, where an entry dp[i][j] is true if a subset of {arr[0], arr[1], …, arr[i-1]} has a sum equal to j.

3. We initialize the column dp[i][0] to true as zero is possible with all subsets. We initialize the first row, dp[0][i], to false as no sum is possible with 0 elements.

4. We fill the partition table in a bottom-up manner.

5. After filling the partition table, the bottom-right corner will give us the largest value j such that dp[arr.length][j] would be true. Using this, we calculate the minimum difference as sum – 2*j.