Subset Sum Problem

The Subset Sum Problem is a classic problem in computer science and is often used to introduce the concept of dynamic programming. Given a set of positive integers and a target sum, the goal is to determine whether there is a subset of the given set that adds up to the target sum.

For example, consider the set of integers [3, 1, 5, 9, 12] and the target sum 8. We can form the subset [3, 5] which adds up to 8.

To solve the Subset Sum Problem using dynamic programming, we can use a 2D array dp of size (n+1) x (targetSum+1), where n is the number of elements in the set. The value dp[i][j] represents whether there is a subset of the first i elements that adds up to the sum j.

We initialize the first row of dp with false values, except for dp[0][0] which is set to true. This represents the case where the sum is 0 and no elements are selected.

Then, we iterate through the elements and the possible sums. If an element arr[i-1] is greater than the current sum j, we copy the value from the previous row dp[i-1][j] to dp[i][j]. Otherwise, we take the logical OR of two conditions:

1. dp[i-1][j]: The current element is not included in the subset.
2. dp[i-1][j-arr[i-1]]: The current element is included in the subset. We subtract the current element from the sum j and check if there is a subset of the previous elements that adds up to this reduced sum.

Finally, the value at dp[n][targetSum] represents whether there is a subset of the entire set that adds up to the target sum.

Here's the Java code to solve the Subset Sum Problem:

1<<code>
2    class Main {
3        /* Returns true if there is a subset of
4        elements in arr[] that has given sum */
5        static boolean isSubsetSum(int[] arr, int n, int sum)
6        {
7            boolean[][] dp = new boolean[n + 1][sum + 1];
8  
9            // If sum is 0, there is always a subset
10            // with 0 elements
11            for (int i = 0; i <= n; i++)
12                dp[i][0] = true;
13  
14            // If sum is not 0 and set is empty,
15            // then answer is false
16            for (int i = 1; i <= sum; i++)
17                dp[0][i] = false;
18  
19            // Fill the subset table in bottom-up manner
20            for (int i = 1; i <= n; i++) {
21                for (int j = 1; j <= sum; j++) {
22                    if (arr[i - 1] > j)
23                        dp[i][j] = dp[i - 1][j];
24                    else
25                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
26                }
27            }
28  
29            return dp[n][sum];
30        }
31  
32        public static void main(String[] args)
33        {
34            int[] arr = { 3, 1, 5, 9, 12 };
35            int sum = 8;
36            int n = arr.length;
37            if (isSubsetSum(arr, n, sum))
38                System.out.println("There is a subset of the given set with the given sum");
39            else
40                System.out.println("No subset of the given set has the given sum");
41        }
42    }