Java Program for Subset Sum Problem using Memoization

Java Program for Subset Sum Problem using Recursion:

Java Program for Subset Sum Problem using Dynamic Programming:

As seen in the previous recursion method, each state of the solution can be uniquely identified using two variables – the index and the remaining sum. So create a 2D array to store the value of each state to avoid recalculation of the same state.

Below is the implementation of the above approach:

Java

// Java program for the above approach
import java.io.*;
class GFG {
 
    // Check if possible subset with
    // given sum is possible or not
    static int subsetSum(int a[], int n, int sum)
    {
        // Storing the value -1 to the matrix
        int tab[][] = new int[n + 1][sum + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                tab[i][j] = -1;
            }
        }
 
        // If the sum is zero it means
        // we got our expected sum
        if (sum == 0)
            return 1;
 
        if (n <= 0)
            return 0;
 
        // If the value is not -1 it means it
        // already call the function
        // with the same value.
        // it will save our from the repetition.
        if (tab[n - 1][sum] != -1)
            return tab[n - 1][sum];
 
        // If the value of a[n-1] is
        // greater than the sum.
        // we call for the next value
        if (a[n - 1] > sum)
            return tab[n - 1][sum]
                = subsetSum(a, n - 1, sum);
        else {
 
            // Here we do two calls because we
            // don't know which value is
            // full-fill our criteria
            // that's why we doing two calls
            if (subsetSum(a, n - 1, sum) != 0
                || subsetSum(a, n - 1, sum - a[n - 1])
                    != 0) {
                return tab[n - 1][sum] = 1;
            }
            else
                return tab[n - 1][sum] = 0;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 5;
        int a[] = { 1, 5, 3, 7, 4 };
        int sum = 12;
 
        if (subsetSum(a, n, sum) != 0) {
            System.out.println("YES\n");
        }
        else
            System.out.println("NO\n");
    }
}
 
// This code is contributed by rajsanghavi9.

Output

YES

Time Complexity: O(sum*n)
Auxiliary space: O(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.

Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

Tags:

#Java Programs