Print all subsequences of a string
You are given a string, you have to print all the subsequences of the string in lexicographical order.
The above problem wants you to print all possible arrangement of the string, that is using string length 1 to maximum valid length and also the string should be in lexicographical order which means according to dictionary appearance or sorted sequence.
The first line of the input consist of T number of test cases, each test case consist of a string str.
You need to print all the subsequences of the given string int lexicographical order separated by new line.
Input: T=1 str="aa" Output: a a aa Input: T=1 str="abc" Output: a ab abc ac b bc c
To solve this problem we will use the backtracking concept along with multiset which will store the subsequences in lexicographical order.
For each character in the given string, it has two options either it will be in the subsequence or will not be in the subsequence, because for this reason, we need to backtrack the solution.
Time Complexity for the above approach in the worst case is exponential.
Output:need an explanation for this answer? contact us directly to get an explanation for this answer