Java Program to Find Sum of All Subsets of a Given Set by Using recursion

Subset sum recursion java – Java Program to Print the Sum of All Subsets of a Given Set of Numbers Using Recursion

by

Subset sum recursion java: In the previous article, we have discussed about Java Program to Find Number of Ways to Express a Number as Sum of Powers by Using Recursion

In this article we are going to see how we can calculate the sum of all subsets of a given set of numbers using recursion by Java programming language.

Java Program to Print the Sum of All Subsets of a Given Set of Numbers Using Recursion

Subset sum java recursion: As per the problem statement given an array of integers, you have to find the sum of all possible subsets.

For example:

Suppose arr[]= {1,2}
Then sum of all subsets = 0, 1 ,2, 3

Lets see a program to understand it more clearly.

Method-1: Java Program to Print the Sum of All Subsets of a Given Set of Numbers By Using Recursion and Static Input Value

Approach:

  • Create an array containing integers.
  • Pass the array to the user defined method subsetSums( ).
  • The user defined method first prints the set then uses recursion to break the set into subset combinations and print individual subset sums.

Program:

import java.util.*;
// Main class
public class Main
{
    // Recursive method to find sum of all subsets
    public static void subsetSums(int[] arr, int left, int right, int sum)
    {
        // Prints the current subset
        if (left > right) 
        {
            System.out.print(sum + " ");
            return;
        }
        // Calculates the subset sum with arr[left] element
        subsetSums(arr, left + 1, right, sum + arr[left]);
        // Calculates the subset sum without arr[left] element
        subsetSums(arr, left + 1, right, sum);
    }

    public static void main(String[] args)
    {
           
        int[] arr = {10,20,30};
        int no = arr.length;
        System.out.print("The subset sums are ");
        // calling the method
        subsetSums(arr,0,no-1,0);
    }
}

Output:

The subset sums are 60 30 40 10 50 20 30 0

Method-2: Java Program to Print the Sum of All Subsets of a Given Set of Numbers By Using Recursion and User Input Value

Approach:

  • Ask the user for number of elements, then insert the elements into an array.
  • Pass the array to the user defined method subsetSums( ).
  • The user defined method first prints the set then uses recursion to break the set into subset combinations and print  individual subset sums.

Program:

import java.util.*;
// Main class
public class Main
{
    // Recursive method to find sum of all subsets
    public static void subsetSums(int[] arr, int left, int right, int sum)
    {
        // Prints the current subset
        if (left > right)
        {
            System.out.print(sum + " ");
            return;
        }
        // Calculates the subset sum with arr[left] element
        subsetSums(arr, left + 1, right, sum + arr[left]);
        // Calculates the subset sum without arr[left] element
        subsetSums(arr, left + 1, right, sum);
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        // Ask the user for input
        System.out.println("Enter number of elements");
        int no = sc.nextInt();
        int[] arr = new int[no];
        // Ask the user to enter the elements
        System.out.println("Enter the elements");
        for(int i = 0; i < no; i++)
        {
            arr[i] = sc.nextInt();
        }
        System.out.print("The subset sums are ");
        // calling the method
        subsetSums(arr,0,no-1,0);
    }
}

Output:

Enter number of elements
3
Enter the elements
1 2 3
The subset sums are 6 3 4 1 5 2 3 0

Interested in programming and want to excel in it by choosing the short ways. Then, practicing with the available Java Program list is mandatory.

Related Java Programs: