Write a program to print all subset of a given string recursively

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. = 23 - 1 = 7 = {NET,NE,NT,N,ET,E,T}
  • 2(number of characters) if we include empty subset. =  23 = 8 = {NET,NE,NT,N,ET,E,T, ϕ }

Approach

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
}

Pictorial Representation

Subset problem

Implementation

/**
 * @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.

Author
Author: Amit Gupta
Published On: 14/10/2016
Last revised On: 15/10/2016
View all articles by Amit Gupta

Share this post

Comments

Comments
comments powered by Disqus

Navigation

Social Media