forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumSumPartition.java
More file actions
89 lines (79 loc) · 1.93 KB
/
MinimumSumPartition.java
File metadata and controls
89 lines (79 loc) · 1.93 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package 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
*/
import java.io.*;
import java.util.*;
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);
}
/**
* 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;
}
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;
}
/** 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;
}
}