Given a string of characters(a-z) ,find subsequence such that every character is strictly greater than all previous characters in that subsequence.
Example if S=abc then there are 7 subsequences which follow the above constraint. These are a,b,c,ab,ac,bc,abc. Notice that we are considering 'a' is smaller than 'b' and so on
Note: A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
We need to find number of such sequences and algo to print all such subsequences.
How to approach this problem ??
You have a string of $n$ characters and you can form the substrings of $1, 2, \cdots, n$ characters.
The number of combinations is for the substring given by
$$ \frac{n!}{k![n-k]!} $$
So you need to calculate
$$ \sum_{k=1}^n \frac{n!}{k![n-k]!} $$
This is
$$ \sum_{k=0}^n \frac{n!}{k![n-k]!} - 1$$
Which can be written as
$$ 2^n - 1 $$