Find All Subsequence of a String in C++ using SET

By srijan bharadwaj

In this tutorial, we will learn how to print all the subsequences of a string using SETs, we will also learn about Sets and how to implement them.

What are the subsequences of a string?

The Subsequences of a string are all the characters that are generated after deleting some letters from a string.

Like for example, let's take a string s="ab".

All Subsequences of this string will be " a ab b ".

How to solve this question?

Well, you can find the solution to this question in many ways like,:-

1. Thinking Recursively i.e Generating all the subsets of a string by fixing characters and then deleting the last letter before every

recursive call.

2. Using the Famous STL Sets(which we will discuss here).

What are Sets?

Sets are associative Containers in STL, which has a property i.e it has all the elements in it unique(non-repeating).

We can also use insert, delete operations In Sets.

How does this Algorithm work?

1.Take a Set.

2.Iterate the String from the front.

3.Iterate the  String from the back and find the substring between them and insert it into the Set.

4. Use another Variable "k" and use it to drop the Kth character of the substring to make a new substring.

5.If the substring is not in the Set then recur bypassing the substring into the function.