More than a Pathshala

In this article we will learn how to write a program to print all subset of a given string recursively.

Let us first understand it with example. Suppose given string be "NET" then total number of subset which can be obtained using the string will be-

- 2
^{(number of characters)}- 1 i.e. = 2^{3}- 1 = 7 = {NET,NE,NT,N,ET,E,T} - 2
^{(number of characters)}if we include empty subset. = 2^{3}= 8 = {NET,NE,NT,N,ET,E,T, ϕ }

At each step, we isolate an `element`

from the remainder and then recursively list those sets that include that element, and recur again to build those sets that don't contain that element. In each case, the set of remaining elements is one smaller and thus represents a slightly easier, smaller version of the same problem. Those recursive calls will eventually lead to the simplest case, that of listing the subsets of an empty set. Here is the pseudocode description:

If there are no more elements remaining, print current subset else { Consider the next element of those remaining Try adding it to the current subset, and use recursion to build subsets from here Try not adding it to current subset, and use recursion to build subsets from here }

/** * @author Amit Gupta * */ public class SubsetPattern { public static void main(String[] args) { recSubsets("", "NET"); } /** This method prints all subset of given string * @param soFar * @param rest */ public static void recSubsets(String soFar, String rest) { if (rest.length() == 0) { System.out.println(soFar); } else { recSubsets(soFar + rest.charAt(0), rest.substring(1)); // include first char recSubsets(soFar, rest.substring(1)); // exclude first char } } }

**Output**

NET NE NT N ET E T

In this article we learnt how to write a program to print all subset of a given string recursively.

Article tagged as

Author

Share this post

Comments