# 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*.