Print all subsequences of a string using ArrayList

Software Development
1

Hello Everyone,

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

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

Alternate Solution: One by one fix characters and recursively generate all subsets starting from them.

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// Function to print all the sub-sequences
// of a string
void printSubSeq(string sub, string ans)
{

if (sub.length() == 0) {
	cout << "" << ans << " ";
	return;
}

// First character of sub
char ch = sub[0];

// Sub-string starting from second
// character of sub
string ros = sub.substr(1);

// Excluding first character
printSubSeq(ros, ans);

// Including first character
printSubSeq(ros, ans + ch);

}

// Driver code
int main()
{
string str = “abc”;
printSubSeq(str, “”);

return 0;

}

Output:

c b bc a ac ab abc