Java Program for Subset Sum Problem using Dynamic Programming

Q: What is Java Program for Subset Sum Problem using Dynamic Programming?

In this article, we will learn Java Program for Subset Sum Problem using Dynamic Programming,This free Java tutorial for complete beginners will help you learn Java from scratch.

Java Program for Subset Sum Problem using Memoization:

Java Program for Subset Sum Problem using Dynamic Programming with space optimization to linear:

We can solve the problem in Pseudo-polynomial time we can use the Dynamic programming approach.

So we will create a 2D array of size (n + 1) * (sum + 1) of type boolean. The state dp[i][j] will be true if there exists a subset of elements from set[0 . . . i] with sum value = ‘j’.

The dynamic programming relation is as follows:

if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]

Below is the implementation of the above approach:

Java

// A Dynamic Programming solution for subset
// sum problem
import java.io.*;
class GFG {
 
    // Returns true if there is a subset of
    // set[] with sum equal to given sum
    static boolean isSubsetSum(int set[], int n, int sum)
    {
        // The value of subset[i][j] will be
        // true if there is a subset of
        // set[0..j-1] with sum equal to i
        boolean subset[][] = new boolean[sum + 1][n + 1];
 
        // If sum is 0, then answer is true
        for (int i = 0; i <= n; i++)
            subset[0][i] = true;
 
        // If sum is not 0 and set is empty,
        // then answer is false
        for (int i = 1; i <= sum; i++)
            subset[i][0] = false;
 
        // Fill the subset table in bottom
        // up manner
        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= n; j++) {
                subset[i][j] = subset[i][j - 1];
                if (i >= set[j - 1])
                    subset[i][j]
                        = subset[i][j]
                        || subset[i - set[j - 1]][j - 1];
            }
        }
 
        return subset[sum][n];
    }
 
    // Driver code
    public static void main(String args[])
    {
        int set[] = { 3, 34, 4, 12, 5, 2 };
        int sum = 9;
        int n = set.length;
        if (isSubsetSum(set, n, sum) == true)
            System.out.println("Found a subset"
                            + " with given sum");
        else
            System.out.println("No subset with"
                            + " given sum");
    }
}
 
/* This code is contributed by Rajat Mishra */

Output

Found a subset with given sum

Time Complexity: O(sum * n), where n is the size of the array.
Auxiliary Space: O(sum*n), as the size of the 2-D array is sum*n.

Java Program for Subset Sum Problem | DP-25

Write a Java program for a given set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.

Examples:

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that adds up to 30.