Print all possible subsequences/subsets in Python

By /
Feature Img Subsequence

In this tutorial, we will be understanding a very interesting problem known as Printing all possible subsequences/subsets of a particular string.

Concept Explained

For every element in the given string, there are two choices:

  • Include the first element in the subsequence and find the subsequence for the remaining elements.
  • Or not include the first element and find the subsequence for the remaining elements.

The same is applied at each and every recursive call until we reach the last index of the given array.

In that case, we just print the subsequence formed and then return to find the next subsequence. If you want to know more about recursion read the tutorial mentioned below.

Read more about Recursion: Recursion in Python

Code Implementation

def get_all_subsequence(n,output,i):       
    if (i==len(n)):
        if (len(output)!=0):
            print(output)
    else:
        # exclude first character
        get_all_subsequence(n,output,i+1)

        # include first character
        output+=n[i]
        get_all_subsequence(n,output,i+1)
    return

n = input()
get_all_subsequence(n,"",0)
print(n[0])

Sample Outputs

All possible subsequences of “abc” string through the code above come out to be as the following:

c
b
bc
a
ac
ab
abc
a

I hope you understood the concept of subsequence or subsets of a string through recursion.

Thank you for reading! Happy learning! 😇