Given a string "s", the task is to find out all non-empty subsequences of it.
A subsequence of a string is a sequence that can be derived from the given string by deleting zero or more elements without changing the order of the remaining elements.
Input: abc
Output: abc, bc, ac, c, ab, b, a
Input : abcd
Output : abcd, bcd, acd, cd, abd, bd, ad, d, abc, bc, ac, c, ab, b, a
Note: For a string of length n, there are a total of 2^n subsequences. Example: "abc" has 2^3 = 8 sub sequences i.e., "abc", "bc", "ac", "c", "ab ", "b", "a", "".
Solutions
Method 1: Using recursion(Backtracking)
This recursive solution is based on the "Pick and Don't Pick Concept".
Begin with the last element and make two calls in each recursion, one while including the current character in the "subsequence (ss)" and one without.
As soon as the input string is exhausted, print "subsequence (ss)" and return.
Complexity
The time complexity of the above recursive solution is exponential (2^n).
In addition, O(n) auxiliary stack space was used for the recursion stack.