MinimumSumPartition.java

packagecom.thealgorithms.dynamicprogramming;

// Partition a set into two subsets such that the difference of subset sums is minimum

/*
Input: arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11

Input: arr[] = {36, 7, 46, 40}
Output: 23
Explanation:
Subset1 = {7, 46} ; sum of Subset1 = 53
Subset2 = {36, 40} ; sum of Subset2 = 76
 */
publicclassMinimumSumPartition {

publicstaticintsubSet(int[] arr) {
intn = arr.length;
intsum = getSum(arr);
boolean[][] dp = newboolean[n + 1][sum + 1];
for (inti = 0; i <= n; i++) {
dp[i][0] = true;
 }
for (intj = 0; j <= sum; j++) {
dp[0][j] = false;
 }

// fill dp array
for (inti = 1; i <= n; i++) {
for (intj = 1; j <= sum; j++) {
if (arr[i - 1] < j) {
dp[i][j] = dp[i - 1][j - arr[i - 1]] || dp[i - 1][j];
 } elseif (arr[i - 1] == j) {
dp[i][j] = true;
 } else {
dp[i][j] = dp[i - 1][j];
 }
 }
 }

// fill the index array
int[] index = newint[sum];
intp = 0;
for (inti = 0; i <= sum / 2; i++) {
if (dp[n][i]) {
index[p++] = i;
 }
 }

returngetMin(index, sum);
 }

/**
 * Calculate sum of array elements
 *
 * @param arr the array
 * @return sum of given array
 */
publicstaticintgetSum(int[] arr) {
intsum = 0;
for (inttemp : arr) {
sum += temp;
 }
returnsum;
 }

publicstaticintgetMin(int[] arr, intsum) {
if (arr.length == 0) {
return0;
 }
intmin = Integer.MAX_VALUE;
for (inttemp : arr) {
min = Math.min(min, sum - 2 * temp);
 }
returnmin;
 }

/**
 * Driver Code
 */
publicstaticvoidmain(String[] args) {
assertsubSet(newint[] { 1, 6, 11, 5 }) == 1;
assertsubSet(newint[] { 36, 7, 46, 40 }) == 23;
assertsubSet(newint[] { 1, 2, 3, 9 }) == 3;
 }
}