C++ Data Structures and Algorithms

Generating subsequences from a string

To find out all subsequences of a string, we need to iterate through all characters of the string. We also create a bit counter variable to mark which element position should be considered to take as a subsequence, also known as a power set. The power set of S is the set of all subsets of S. Suppose we have three characters in a string, which are xyz. The power set of the string will be 2ⁿ elements, which is as follows:

BIT -> SUBSET===================000 -> Empty subset001 -> "x"010 -> "y"011 -> "xy"100 -> "z"101 -> "xz"110 -> "yz"111 -> "xyz"

By using the power set, we can create the code to generate subsequence of a string, as follows:

vector<string> GenerateSubsequences(    string str){ // Return value ...