10. Print all the Subsequence of a String

10. Print all the Subsequence of a String

Problem link :- clic here

package programs;

import java.util.ArrayList;

public class String__10
{

	/*
	 	Print all the subsequences of a string
	 			str = "xyz"
	 		output = { " ",  "x",  "y",  "z",  "xy",  "yz",  "xz",  "xyz" }
	 	
	 	lets us return the subsequences in an array or ArrayList
	 	this problem will be similar to all lengths of strings
	 	so lets do it in RECURSIVELY 
	 	
	 	if a string is empty then its subSequence  is only one        {  " "  }
	 	if only one character in that string str = "x"                    { " ", "x"}
	 	if 2     str = "xy"							{" ", "x", "y", "yx"}
	 	if 3     str = "xyz" 			{ " ", "x", "y", "yx", "z", "zx", "zy", "zyx"}
	 	
	 	As we are adding a character in the string
	 	we are just copying the subsequences of previous string 
	 	and also adding that character you added to the string to each and 
	 		every substring of the previous string
	 */
	
	static String[] subsequencesOfString(String str)
	{
		if(str.length() == 0)
		{
			String ans[] = {" "};
			return ans;
		}
		
		//we will call the function recursively with a substring 
		//which has all the characters of the string          but not first character
		String previousAns[] = subsequencesOfString( str.substring(1) );
		
		//the size of the array that we are returning we will be double
		//the size of the previousAns 
		//because we are 1) copying all the subsequences
		//			      2) adding the first character to each & every subsequence
		
		int n = previousAns.length;
		String ans[] = new String[2 * n];    //our output
		
		//copying
		int k = 0;
		for(int i=0; i<n; i++)
			ans[k++] = previousAns[i];
		
		for(int j=0; j<n; j++)
			ans[k++] = str.charAt(0)  + previousAns[j];
		
		return ans;
	}

	static void printSubsequences(String str, String s)
	{
		if(str.length() == 0)
		{
			System.out.print(s + " ");
			return;
		}
		
		char x = str.charAt(0);
		//not involving first character
		printSubsequences(str.substring(1), s);
		
		//involving first character
		printSubsequences(str.substring(1), s+x);
	}
	
	
	public static void main(String[] args)
	{
		String str = "xyz";
		String ans[] = subsequencesOfString(str);
		
		for(int i=0; i<ans.length; i++)
			System.out.print(ans[i] + " ");
		
		System.out.println("\nThis is uising printSubsequences : ");
		printSubsequences(str, " ");
	}

}

Time complexity :- O()
Space complexity :- O()