This Java program generates all subsets of a given array that sum to a specified target. The program uses a backtracking approach to explore all possible subsets.

Program Explanation

The program consists of the following components:

• Main Class: The SubsetSum class contains the main method and initiates the process of generating subsets.
• Method for Finding Subsets: The findSubsetsWithSum method is a recursive function that explores subsets and checks their sums.
• Utility Method: The printSubset method is used to print the valid subsets that match the target sum.

Java Code

import java.util.ArrayList;
import java.util.List;

public class SubsetSum {

    // Method to find all subsets that sum to the target
    public static void findSubsetsWithSum(int[] arr, int target, List currentSubset, int index) {
        // Base case: if we reach the end of the array
        if (index == arr.length) {
            // Check if the current subset sums to the target
            int currentSum = 0;
            for (int num : currentSubset) {
                currentSum += num;
            }
            if (currentSum == target) {
                printSubset(currentSubset);
            }
            return;
        }

        // Include the current element in the subset
        currentSubset.add(arr[index]);
        findSubsetsWithSum(arr, target, currentSubset, index + 1);

        // Exclude the current element from the subset
        currentSubset.remove(currentSubset.size() - 1);
        findSubsetsWithSum(arr, target, currentSubset, index + 1);
    }

    // Method to print the subset
    public static void printSubset(List subset) {
        System.out.println(subset);
    }

    // Main method to run the program
    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 5, 4};
        int targetSum = 6;

        System.out.println("Subsets with sum " + targetSum + ":");
        findSubsetsWithSum(arr, targetSum, new ArrayList<>(), 0);
    }
}

Explanation of the Code

1. Main Class: The SubsetSum class contains the main method, where execution begins. It initializes the array and the target sum.
2. Finding Subsets: The findSubsetsWithSum method recursively explores all combinations of the array. It includes or excludes each element and checks if the current subset’s sum equals the target.
3. Printing Subsets: The printSubset method outputs any subset that meets the target sum.
4. Running the Program: The instructions on how to compile and run the program are included, guiding users through the process.

How to Run the Program

1. Copy the code into a Java file named SubsetSum.java.
2. Compile the Java file using javac SubsetSum.java.
3. Run the compiled class with java SubsetSum.

Output

When you run the program with the provided array and target sum, it will output all subsets that sum to the target. For example:

Subsets with sum 6:
[3, 1, 2]
[2, 4]
[1, 5]