A string s is given, the task is to print all subsequences of s using recursion. Every string of size n will have 2^n subsequences.
Example 1: Print subsequences of "abc".
Input: "abc"
Output:
c b bc a ac ab abc
Example 2: Print subsequences of "vxyz".
Input: "vxyz"
Output:
z y yz x xz xy xyz v vz vy vyz vx vxz vxy vxyz
Solutions
Method 1: Recursion
As the pattern shows - to obtain any subsequence we are either choosing a character or dropping a character. This is exactly, what we need to do here, we will run the fn recursively twice, once including the current value in subsequence and other without including the current value in subsequence.
As soon as the iteration is complete we will print the subsequence.
package com.cb.recursion;
public class R11_SubSequence {
public static void printSubSequence(String s, int index, String subString) {
if (index >= s.length()) {
System.out.println(subString);
return;
}
// not taking current character
printSubSequence(s, index + 1, subString);
// taking current character
subString += s.charAt(index);
printSubSequence(s, index + 1, subString);
}
public static void main(String[] args) {
printSubSequence("abc", 0, "");
}
}
c b bc a ac ab abc
Complexity
For every element two recursive case originates, so Time Complexity is O(2^n). For each character we need to store values in two strings (subsequence), so Space Complexity is O(2^n).