Print all subsequences of a string using ArrayList

Given a string str, the task is to print all the sub-sequences of str.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Examples:

Input: str = “abc”
Output: a b ab c ac bc abc

Input: str = “geek”
Output: g e ge e ge ee gee k gk ek gek ek gek eek geek

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: Write a recursive function that prints every sub-sequence of the sub-string starting from the second character str[1, n – 1] after appending the first character of the string str[0] in the beginning of every sub-sequence. Terminating condition will be when the passed string is empty, in that case the function will return an empty arraylist.

Below is the implementation of the above approach:

// Java implementation of the approach 

import java.util.ArrayList; 

public class GFG { 

// Utility function to print the contents 

// of the ArrayList 

static void printArrayList(ArrayList<String> arrL) 

{ 

arrL.remove(""); 

for (int i = 0; i < arrL.size(); i++) 

System.out.print(arrL.get(i) + " "); 

} 

// Function to returns the arraylist which contains 

// all the sub-sequences of str 

public static ArrayList<String> getSequence(String str) 

{ 

// If string is empty 

if (str.length() == 0) { 

// Return an empty arraylist 

ArrayList<String> empty = new ArrayList<>(); 

empty.add(""); 

return empty; 

} 

// Take first character of str 

char ch = str.charAt(0); 

// Take sub-string starting from the 

// second character 

String subStr = str.substring(1); 

// Recurvise call for all the sub-sequences 

// starting from the second character 

ArrayList<String> subSequences = 

getSequence(subStr); 

// Add first character from str in the beginning 

// of every character from the sub-sequences 

// and then store it into the resultant arraylist 

ArrayList<String> res = new ArrayList<>(); 

for (String val : subSequences) { 

res.add(val); 

res.add(ch + val); 

} 

// Return the resultant arraylist 

return res; 

} 

// Driver code 

public static void main(String[] args) 

{ 

String str = "geek"; 

printArrayList(getSequence(str)); 

// System.out.print(getSequence(str)); 

} 

} 

Output:

g e ge e ge ee gee k gk ek gek ek gek eek geek