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)**.