Solve the Balanced Partition problem using dynamic programming.?

The Balanced Partition problem can be briefly defined as follows: Given a set of integers, divide it into two subsets such that the difference between the sum of the elements in each subset is minimized.

This problem can be solved using dynamic programming. The idea is to use a table to store solutions to subproblems, which we can then use to build up the solution to the original problem. Let’s define the table as follows:

1. Rows represent the elements in the original set (including the empty set).

2. Columns represent the possible subsets (including the empty subset).

3. Entry (i,j) represents whether it is possible to form a subset of j elements from the first i elements of the set.

For example, let’s consider the set 3, 1, 1, 2, 2, 1. One possible subset is 3, 1, 2, which has a sum of 6. We can represent this subset in the table as follows:

|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
|   | T | F | F | F | F | F | F |
| 3 | T | F | F | T | F | F | F |
| 1 | T | T | F | T | T | F | F |
| 1 | T | T | T | T | T | T | F |
| 2 | T | T | T | T | T | T | T |
| 2 | T | T | T | T | T | T | T |
| 1 | T | T | T | T | T | T | T |

In this case, since there are six elements in the set, we have a 6 x 7 table. The first row represents the empty set, and it is always possible to form a subset of 0 elements from the empty set. The first column represents the empty subset, and it is always possible to form an empty subset from any set. Entries in other rows and columns are calculated as follows:

1. If we are trying to form a subset of size 0, it is always possible to do so.

2. If we are trying to form a subset from the first i elements of the set, and the sum of those i elements is less than j, then it is not possible to form a subset of size j.

3. Otherwise, we can form a subset of size j either by including the i-th element and forming a subset of size j-1 from the first i-1 elements, or by not including the i-th element and forming a subset of size j from the first i-1 elements.

Once we have calculated the entire table, we can use it to find the solution to the original problem, which is the minimum difference between the sums of two subsets. We do this by finding the largest possible subset sum that is less than or equal to half the total sum of the set. This is the sum of the largest subset that can be formed, and we can subtract it from the total sum to get the sum of the smallest subset. In other words, if the total sum is S and the largest possible subset sum is s, then the solution is |S - 2s|.

Here’s the Java code to implement this algorithm:

public static int balancedPartition(int[] set) {
    int n = set.length;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += set[i];
    }
    boolean[][] table = new boolean[n+1][sum/2+1];
    for (int i = 0; i <= n; i++) {
        table[i][0] = true;
    }
    for (int j = 1; j <= sum/2; j++) {
        table[0][j] = false;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum/2; j++) {
            if (set[i-1] <= j) {
                table[i][j] = table[i-1][j] || table[i-1][j-set[i-1]];
            } else {
                table[i][j] = table[i-1][j];
            }
        }
    }
    int s = 0;
    for (int j = sum/2; j >= 0; j--) {
        if (table[n][j]) {
            s = j;
            break;
        }
    }
    return Math.abs(sum - 2*s);
}

The ‘balancedPartition‘ method takes an integer array ‘set‘ as input, and returns the minimum difference between the sums of two subsets. The algorithm works as follows:

1. First, it calculates the total sum of the set and initializes the table with ‘true‘ for the entries corresponding to subsets of size 0.

2. Then, it loops over each possible subset size and each element of the set, calculating whether it is possible to form a subset of the given size from the first i elements of the set.

3. Once the entire table has been filled, it loops over the possible subset sums to find the largest one that is less than or equal to half the total sum of the set.

4. Finally, it returns the difference between the total sum and twice the largest possible subset sum.

The time complexity of this algorithm is O(n * sum), where n is the size of the set and sum is the total sum of the set. The space complexity is also O(n * sum), since we need to store a boolean value for each possible combination of element and subset sum.