What is Java Program for Subset Sum Problem using Recursion?

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

Java Program for Subset Sum Problem using Recursion

Java Program for Subset Sum Problem using Memoization:

For the recursive approach, there will be two cases.

Consider the ‘last’ element to be a part of the subset. Now the new required sum = required sum – value of ‘last’ element.

Don’t include the ‘last’ element in the subset. Then the new required sum = old required sum.

In both cases, the number of available elements decreases by 1.

Step-by-step approach:

Build a recursive function and pass the index to be considered (here gradually moving from the last end) and the remaining sum amount.
For each index check the base cases and utilize the above recursive call.
If the answer is true for any recursion call, then there exists such a subset. Otherwise, no such subset exists.

Below is the implementation of the above approach.

Java

// A recursive solution for subset sum
 
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)
    {
        // Base Cases
        if (sum == 0)
            return true;
        if (n == 0)
            return false;
 
        // If last element is greater than
        // sum, then ignore it
        if (set[n - 1] > sum)
            return isSubsetSum(set, n - 1, sum);
 
        // Else, check if sum can be obtained
        // by any of the following
        // (a) including the last element
        // (b) excluding the last element
        return isSubsetSum(set, n - 1, sum)
            || isSubsetSum(set, n - 1, sum - set[n - 1]);
    }
 
    // 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(2ⁿ)
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.