Skip to content

#4387 Enhance Minimum sum partition problem implementation #4394

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 8 commits into from
Sep 23, 2023
Merged

#4387 Enhance Minimum sum partition problem implementation #4394

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
8bde8a1
Enhance Minimum sum partition problem implementation
Manan-09 Sep 21, 2023
ea00af0
Linter resolved
Manan-09 Sep 21, 2023
4d6a61a
Linter resolved
Manan-09 Sep 21, 2023
a330058
Code review comments
Manan-09 Sep 22, 2023
2017a58
Code review comments
Manan-09 Sep 22, 2023
5462934
Add validation for non-negative numbers
Manan-09 Sep 23, 2023
5762896
Linter resolved
Manan-09 Sep 23, 2023
ade462b
style: fix formiatting
vil02 Sep 23, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
106 changes: 37 additions & 69 deletions src/main/java/com/thealgorithms/dynamicprogramming/MinimumSumPartition.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,89 +1,57 @@
package com.thealgorithms.dynamicprogramming;

// Partition a set into two subsets such that the difference of subset sums is minimum
import java.util.Arrays;

/*
Input: arr[] = {1, 6, 11, 5}
Output: 1
Given an array of non-negative integers , partition the array in two subset that
difference in sum of elements for both subset minimum.
Return the minimum difference in sum of these subsets you can achieve.

Input: array[] = {1, 6, 11, 4}
Output: 0
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset1 = {1, 4, 6}, sum of Subset1 = 11
Subset2 = {11}, sum of Subset2 = 11

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

public static int subSet(int[] arr) {
int n = arr.length;
int sum = getSum(arr);
boolean[][] dp = new boolean[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int j = 0; j <= sum; j++) {
dp[0][j] = false;
}

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

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

return getMin(index, sum);
public final class MinimumSumPartition {
private MinimumSumPartition() {
}

/**
* Calculate sum of array elements
*
* @param arr the array
* @return sum of given array
*/
public static int getSum(int[] arr) {
int sum = 0;
for (int temp : arr) {
sum += temp;
private static void throwIfInvalidInput(final int[] array) {
if (Arrays.stream(array).anyMatch(a -> a < 0)) {
throw new IllegalArgumentException("Input array should not contain negative number(s).");
}
return sum;
}

public static int getMin(int[] arr, int sum) {
if (arr.length == 0) {
return 0;
}
int min = Integer.MAX_VALUE;
for (int temp : arr) {
min = Math.min(min, sum - 2 * temp);
}
return min;
}
public static int minimumSumPartition(final int[] array) {
throwIfInvalidInput(array);
int sum = Arrays.stream(array).sum();
boolean[] dp = new boolean[sum / 2 + 1];
dp[0] = true; // Base case , don't select any element from array

/**
* Driver Code
*/
public static void main(String[] args) {
assert subSet(new int[] {1, 6, 11, 5}) == 1;
assert subSet(new int[] {36, 7, 46, 40}) == 23;
assert subSet(new int[] {1, 2, 3, 9}) == 3;
// Find the closest sum of subset array that we can achieve which is closest to half of sum of full array
int closestPartitionSum = 0;

for (int i = 0; i < array.length; i++) {
for (int j = sum / 2; j > 0; j--) {
if (array[i] <= j) {
dp[j] = dp[j] || dp[j - array[i]];
}
if (dp[j]) {
closestPartitionSum = Math.max(closestPartitionSum, j);
}
}
}
/*
Difference in sum = Big partition sum - Small partition sum
= ( Total sum - Small partition sum) - Small partition sum
*/
return sum - (2 * closestPartitionSum);
}
}
44 changes: 44 additions & 0 deletions src/test/java/com/thealgorithms/dynamicprogramming/MinimumSumPartitionTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,44 @@
package com.thealgorithms.dynamicprogramming;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.Test;

class MinimumSumPartitionTest {
@Test
public void testMinimumSumPartitionWithEvenSum() {
int[] array = {1, 6, 11, 4};
assertEquals(0, MinimumSumPartition.minimumSumPartition(array));
}

@Test
public void testMinimumSumPartitionWithOddSum() {
int[] array = {36, 7, 46, 40};
assertEquals(23, MinimumSumPartition.minimumSumPartition(array));
}

@Test
public void testMinimumSumPartitionWithSingleElement() {
int[] array = {7};
assertEquals(7, MinimumSumPartition.minimumSumPartition(array));
}

@Test
public void testMinimumSumPartitionWithLargeNumbers() {
int[] array = {100, 200, 300, 400, 500};
assertEquals(100, MinimumSumPartition.minimumSumPartition(array));
}

@Test
public void testMinimumSumPartitionWithEmptyArray() {
int[] array = {};
assertEquals(0, MinimumSumPartition.minimumSumPartition(array));
}

@Test
public void testMinimumSumPartitionThrowsForNegativeArray() {
int[] array = {4, 1, -6, 7};
assertThrows(IllegalArgumentException.class, () -> { MinimumSumPartition.minimumSumPartition(array); });
}
}