Print Subsequences

Moderate

0/80

Contributed by

42 upvotes

Problem statement

Given a string 'S' of length 'N', return all the subsequences of the given string.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Note :

You may return the subsequences in any order but they will be printed in lexicographically ascending order.

If a string from the returned array has a length of zero, it will be represented as 'Empty String' in the output.

For Example:

For a given word “cn” the possible subsequences are 'Empty String', 'c', 'cn' and 'n'.

We get :
'Empty String' by deleting 'c' and 'n'.
'c' by deleting 'n'.
'n' by deleting 'c'.
'cn' if we don't delete any thing.

Detailed explanation ( Input/output format, Notes, Images )

Input format

The input only consists of one line which consists of a single string

Output format

The output consists of all subsequences of the input string where each subsequence is printed in a different line which is sorted in lexicographically ascending order.

Sample Input 1:

abc

Sample Output 1:

'Empty String'
a
ab
abc
ac
b
bc
c

Sample Input 2:

Sample Output 2:

'Empty String'
f

Constraints

1 <= N <= 15
where 'N' represents the length of the input string 'S'

Time limit: 1 sec

Console