Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.
Examples:
Input : abc Output : a, b, c, ab, bc, ac, abc Input : aaa Output : a, aa, aaa
Using Pick and Don’t Pick concept :
Python3
def printSubSequences(STR, subSTR=""): """ function: To print all subsequences of string concept: Pick and Don’t Pick variables: STR = string subSTR = to store subsequence """ if len(STR) == 0: print(subSTR, end=" ") return # we add adding 1st character in string printSubSequences(STR[:-1], subSTR + STR[-1]) """ Not adding first character of the string because the concept of subsequence either character will present or not """ printSubSequences(STR[:-1], subSTR) returndef main(): """ main function to drive code """ STR = "abc" printSubSequences(STR)if __name__ == "__main__": main()# by itsvinayak |
Output:
cba cb ca c ba b a
Time Complexity:
The time complexity of this algorithm is O(2^n) because we are making 2 recursive calls for each character of the string, i.e. one with the character included in the subsequence and the other one without the character.
Space Complexity:
The space complexity of this algorithm is O(n) because we are using recursive calls to print the subsequences, which will be stored on the stack.
pythonic implementations:
Prerequisite: itertools.combinations() module in Python to print all possible combinations
Python3
# Python Implementation of the approachimport itertoolsdef Sub_Sequences(STR): combs = [] for l in range(1, len(STR)+1): combs.append(list(itertools.combinations(STR, l))) for c in combs: for t in c: print (''.join(t), end =' ')# Testing with driver codeif __name__ == '__main__': Sub_Sequences('abc') |
a b c ab ac bc abc
