Subsequence string is a string derived from another string by deleting some characters without changing the order of the remaining characters. Suppose we have a string: donut. The subsequences of this word would be—d, o, do, n, dn, on, don, u, du, ou, dou, nu, dnu, onu, donu, t, dt, ot, dot, nt, dnt, ont, dont, ut, dut, out, dout, nut, dnut, onut, and donut.
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 2n elements, which is as follows:
BIT -> SUBSET =================== 000 -> Empty subset 001 -> "x" 010 -> "y" 011 -> "xy" 100 -> "z" 101 -> "xz" 110 -> "yz" 111 -> "xyz"
By...