1. Introduction

In Java, finding all subsets of a string is a common problem that can be solved using recursion. A string of length n has 2^n subsets, including the empty set and the string itself. In this post, we will explore a Java program to find all subsets of a given string.

2. Program Steps

1. Define a main method to serve as the entry point of the program.

2. Declare and initialize the input string whose subsets we intend to find.

3. Call a recursive method, findAllSubsets, passing the initial string and an empty string to start the subset accumulation.

4. In findAllSubsets, print the current subset and recursively call the function twice: once including the next character in the subset and once without it.

5. Observe the output, which will display all subsets of the input string.

3. Code Program

public class StringSubsets {

    public static void main(String[] args) {
        // Step 2: Initialize the string whose subsets we wish to find
        String input = "ABC";

        // Step 3: Start the recursive function to find all subsets
        findAllSubsets(input, "");
    }

    public static void findAllSubsets(String str, String subset) {
        // If the string is empty, print the subset and return
        if (str.length() == 0) {
            // Print the current subset
            System.out.println(subset);
            return;
        }

        // Step 4: Call the function recursively, once without including the current character
        // and once including it
        findAllSubsets(str.substring(1), subset + str.charAt(0));
        findAllSubsets(str.substring(1), subset);
    }
}

Output:

ABC
AB
AC
A
BC
B
C
(empty string)

4. Step By Step Explanation

– Step 1: We start by defining the main method which serves as the entry point of our program.

– Step 2: The string "ABC" is initialized, and we aim to find all its subsets.

– Step 3: We invoke the findAllSubsets method with the initial string and an empty string to begin forming subsets.

– Step 4: In each recursive call, we consider including or excluding the current character and call findAllSubsets accordingly until the input string becomes empty. When the string is empty, we print the subset formed.

– Step 5: The output of the program is all the subsets of the given input string, including the empty string.

This approach efficiently computes all possible subsets of a string in Java, providing a clear demonstration of recursion and string manipulation.