Python Code for Printing all Possible subsequences/subsets.

Let us look at a highly exciting subject called Printing all possible subsequences/subsets of a given string.

There are two options for each element in the specified string:

Include the first element in the subsequence and then determine the subsequence for the other elements.
Alternatively, leave out the first element and determine the subsequence for the remaining elements.
The same logic is used in each recursive call until we reach the last index of the provided array.

In that scenario, we just print the created subsequence and then return to identify the next subsequence.

Python Code

Method #1: Using Recursive Function (Static Input)

Approach:

  • Give the string as static input and store it in a variable.
  • Create a recursive function say possible_subsequences() which accepts the given string, result string, and index pointing for the given string as the arguments and returns all the subsequences or subsets of a given string.
  • Inside the possible_subsequences() function, check if the index argument(k) is equal to the given length of the string or not using the if conditional statement.
  • If it is true, then check if the length of the result string is not equal to 0 using the if conditional statement.
  • If it is true, then print the result string.
  • Else, Pass the given string, result string, and k+1 for the function itself(recursive logic). It excludes the first character.
  • Add the given string at the index k to the result string and store it in the same variable.
  • Pass the given string, result string, and k+1 for the function itself(recursive logic). It includes the first character.
  • Return.
  • Pass the given string, empty string and 1st index(0) to the recursive function possible_subsequences().
  • Print the first character of the given string.
  • The Exit of the Program.

Below is the implementation:

# Create a recursive function say possible_subsequences() which accepts the
# given string, result string, and index pointing for the given string as
# the arguments and returns all the subsequences or subsets of a given string.


def possible_subsequences(gvn_str, rslt, k):
    # Inside the possible_subsequences() function, check if the index argument(k)
        # is equal to the given length of the string or not using the if conditional
        # statement.
    if (k == len(gvn_str)):
        # If it is true, then check if the length of the result string is not equal
                # to 0 using the if conditional statement.
        if (len(rslt) != 0):
          # If it is true, then print the result string.
            print(rslt)
    else:
        # Else, Pass the given string, result string, and k+1 for the function itself
                # (recursive logic). It excludes the first character.
        possible_subsequences(gvn_str, rslt, k+1)

        # Add the given string at the index k to the result string and store it in
        # the same variable.It includes the first character.
        rslt += gvn_str[k]
        # Pass the given string, result string, and k+1 for the function itself
        # (recursive logic).
        possible_subsequences(gvn_str, rslt, k+1)
    # Return.
    return


# Give the string as static input and store it in a variable.
gvn_str = "pqr"
print("The all possible subsequences of a given string are :")
# Pass the given string, empty string and 1st index(0) to the recursive function
# possible_subsequences().
possible_subsequences(gvn_str, "", 0)
# Print the first character of the given string.
print(gvn_str[0])

Output:

The all possible subsequences of a given string are :
r
q
qr
p
pr
pq
pqr
p

Method #2: Using Recursive Function (User Input)

Approach:

  • Give the string as user input using the input() function and store it in a variable.
  • Create a recursive function say possible_subsequences() which accepts the given string, result string, and index pointing for the given string as the arguments and returns all the subsequences or subsets of a given string.
  • Inside the possible_subsequences() function, check if the index argument(k) is equal to the given length of the string or not using the if conditional statement.
  • If it is true, then check if the length of the result string is not equal to 0 using the if conditional statement.
  • If it is true, then print the result string.
  • Else, Pass the given string, result string, and k+1 for the function itself(recursive logic). It excludes the first character.
  • Add the given string at the index k to the result string and store it in the same variable.
  • Pass the given string, result string, and k+1 for the function itself(recursive logic). It includes the first character.
  • Return.
  • Pass the given string, empty string and 1st index(0) to the recursive function possible_subsequences().
  • Print the first character of the given string.
  • The Exit of the Program.

Below is the implementation:

# Create a recursive function say possible_subsequences() which accepts the
# given string, result string, and index pointing for the given string as
# the arguments and returns all the subsequences or subsets of a given string.


def possible_subsequences(gvn_str, rslt, k):
    # Inside the possible_subsequences() function, check if the index argument(k)
        # is equal to the given length of the string or not using the if conditional
        # statement.
    if (k == len(gvn_str)):
        # If it is true, then check if the length of the result string is not equal
                # to 0 using the if conditional statement.
        if (len(rslt) != 0):
          # If it is true, then print the result string.
            print(rslt)
    else:
        # Else, Pass the given string, result string, and k+1 for the function itself
                # (recursive logic). It excludes the first character.
        possible_subsequences(gvn_str, rslt, k+1)

        # Add the given string at the index k to the result string and store it in
        # the same variable.It includes the first character.
        rslt += gvn_str[k]
        # Pass the given string, result string, and k+1 for the function itself
        # (recursive logic).
        possible_subsequences(gvn_str, rslt, k+1)
    # Return.
    return


# Give the string as user input using the input() function and store it in a variable.
gvn_str = input("Enter some random string = ")
print("The all possible subsequences of a given string are :")
# Pass the given string, empty string and 1st index(0) to the recursive function
# possible_subsequences().
possible_subsequences(gvn_str, "", 0)
# Print the first character of the given string.
print(gvn_str[0])

Output:

Enter some random string = xyz
The all possible subsequences of a given string are :
z
y
yz
x
xz
xy
xyz
x