Be the first user to complete this post

  • 0
Add to List
Medium

259. Print all sub sequences of a given String

Objec­tive:  Given a String write an algorithm to print all the possible sub-subsequences.

Example:

String input = “abc”;

Output: Possible sub sequences –
{Empty}, {a}, {b}, {c}, {ab} ,{a,c}, {b, c}, {a, b, c}

Approach:

  • The approach will be similar to as discussed here Gen­er­ate All Strings of n bits.
  • If we consider n= 3(same as the string length) then all possible combinations are [0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1].
  • So from the above combinations, wherever the bit is set to 1, place a string character from the index (same as position) at the position, and wherever the bit is set to 0, ignore the string character at the index.
  • The above step will give the desired result.
  • See the code below for better understanding.

Time Complexity: O(2^n)

 

Output:

a b c
a b
a c
a
b c
b
c
{Empty Set}