Solve the Subset Sum problem using dynamic programming.?

The Subset Sum problem is a classic problem in computer science that involves finding whether a subset of integers in an array sum up to a given target sum. The problem is NP-complete, so we cannot solve it using a brute-force approach for large inputs. However, we can use dynamic programming to find an efficient solution.

The approach for solving the Subset Sum problem using dynamic programming involves creating a boolean matrix where each row represents an element from the array and each column represents a sum from 0 to the target sum. The value at each cell (i,j) in the matrix is true if it is possible to obtain the sum j using elements up to the ith position in the array, otherwise it is false.

To fill this matrix, we need to consider two cases:

1. If we exclude the ith element from the sum, we can see whether we can get the sum without the ith element, by looking at the value in the row above.

2. If we include the ith element in the sum, we can obtain the sum by adding the ith element to the sum (j-ith element), which is in the (i-1, j - arr[i]) cell.

After filling the matrix, we need to find a true value in the last row of the matrix, starting from the target sum. If such a value exists, it means that it is possible to obtain the sum using some elements from the array.

Here’s the Java code implementation for solving the Subset Sum problem using dynamic programming:

public static boolean subsetSum(int[] arr, int targetSum) {
    int n = arr.length;

    boolean[][] dp = new boolean[n+1][targetSum+1];

    for(int i=0; i<=n; i++) {
        dp[i][0] = true;
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=targetSum; j++) {
            if(arr[i-1] <= j) {
                dp[i][j] = dp[i-1][j-arr[i-1]] || dp[i-1][j];
            }
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    return dp[n][targetSum];
}

Let’s take an example to understand how this code works. Consider an array 3, 7, 4, 2 and target sum is 5. The boolean matrix after filling will look like:

i/j   0   1   2   3   4   5
0     T   F   F   F   F   F
1     T   F   F   T   F   F
2     T   F   F   T   F   F
3     T   F   T   T   T   T
4     T   F   T   T   T   T

As we can see, the value at dp[4][5] is true, which means it is possible to obtain the sum of 5 using elements from the array 3, 7, 4, 2.

Therefore, we have solved the Subset Sum problem using dynamic programming.