Recursion-Subsequences

 Take as input str, a string. We are concerned with all the possible subsequences of str. E.g.

a. Write a recursive function which returns the count of subsequences for a given string. Print the value returned.

b. Write a recursive function which prints all possible subsequences for a “abcd” has following subsequences “”, “d”, “c”, “cd”, “b”, “bd”, “bc”, “bcd”, “a”, “ad”, “ac”, “acd”, “ab”, “abd”, “abc”, “abcd”.given string (void is the return type for function).
Note: Use cin for input for C++

Input Format

Enter a string

Constraints

None

Output Format

Print all the subsequences in a space separated manner and isplay the total no. of subsequences.

Sample Input

abcd

Sample Output

 d c cd b bd bc bcd a ad ac acd ab abd abc abcd 
16

Explanation

Print all possible subsequences of the given string.



import java.util.Scanner;

public class Main {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
String inputString = s.next();
returnSubsquence(inputString, "");
System.out.println("\n"+returnSubsquenceCount(2,inputString.length()));
s.close();

}

private static void returnSubsquence(String inputString, String ans) {
if (inputString.length() == 0) {
System.out.print(ans+" ");
return;
}
char firstChar = inputString.charAt(0);
returnSubsquence(inputString.substring(1), ans);
returnSubsquence(inputString.substring(1), ans+firstChar);

}

private static int returnSubsquenceCount(int b,int e)
{
if(e==0)
{
return 1;
}
return b*returnSubsquenceCount(b,e-1);
}
}