Given a set of integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.
If there is a set S with n elements, then if we assume Subset1 has m elements, Subset2 must have n-m elements and the value of abs(sum(Subset1) – sum(Subset2)) should be minimum.
Example:
Input: arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11
Solution:
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
public class MinimumSubsetSumDifference {
public static int minSubsetSumDifference(int[] w, int n) {
int c = 0;
for (int i : w) {
c += i;
}
int x = c;
c = c / 2;
int[][] dp = new int[n + 1][c + 1];
for (int i = 1; i <= w.length; i++) {
for (int j = 1; j <= c; j++) {
if (w[i - 1] <= j) {
dp[i][j] = Math.max(w[i - 1] + dp[i - 1][j - w[i - 1]],
dp[i - 1][j]
);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return x - 2 * dp[w.length][c];
}
}