Generate all possible sub-sequence of a string.

The article is about how can we generate all possible sub-sequence of a given string. From this question I started my journey to Recursion !

Input: “ ABC”
Output: “ABC”, “AB”, “AC”, “ A”, “ BC”, “ B”, “C”

Intuition: Recursion is similar to Mathematical Induction where we know the output of a function for a given base case input i.e. for (n = 1), we have to deduce a formula for any general input (n = k) and then the recursion will generate the output for ( n = k+1).

Base Case: we know that for empty string s = “” our function should return an empty string i.e. f(s, ans) = “” .
Intuitive Step: we have to formalise a recursive step for given s ! = “”.
f(s, ans) = f(s[1:], ans + s[0]), f(s[1:], ans)
Recursive Step: recursion will bring you the answer for rest of the problem

Here is the Python Code snippet of the above problem

def generateAllSubstr(s, ans):
   if len(s) == 0:
      print(ans)
      return ''
   generateAllSubstr(s[1:], ans + s[0])
   generateAllSubstr(s[1:], ans)

This is the recursive Tree Diagram for the Sub-sequence problem.