Print all subsequences of a string | Iterative Method | Java program to print all Subsequences of a String in iterative manner ; Function to find subsequence ; Check if jth bit in binary is 1 ; If jth bit is 1 , include it in subsequence ; Function to print all subsequences ; Map to store subsequence lexicographically by length ; Total number of non - empty subsequence in String is 2 ^ len - 1 ; i = 0 , corresponds to empty subsequence ; Subsequence for binary pattern i ; Storing sub in map ; it . first is length of Subsequence it . second is set < String > ; ii is iterator of type set < String > ; Driver code
import java . util . ArrayList ; import java . util . Arrays ; import java . util . HashMap ; import java . util . HashSet ; import java . util . Map ; import java . util . SortedMap ; import java . util . TreeMap ; class Graph { static String subsequence ( String s , int binary , int len ) { String sub = " " ; for ( int j = 0 ; j < len ; j ++ ) if ( ( binary & ( 1 << j ) ) != 0 ) sub += s . charAt ( j ) ; return sub ; } static void possibleSubsequences ( String s ) { SortedMap < Integer , HashSet < String > > sorted_subsequence = new TreeMap < Integer , HashSet < String > > ( ) ; int len = s . length ( ) ; int limit = ( int ) Math . pow ( 2 , len ) ; for ( int i = 1 ; i <= limit - 1 ; i ++ ) { String sub = subsequence ( s , i , len ) ; if ( ! sorted_subsequence . containsKey ( sub . length ( ) ) ) sorted_subsequence . put ( sub . length ( ) , new HashSet < > ( ) ) ; sorted_subsequence . get ( sub . length ( ) ) . add ( sub ) ; } for ( Map . Entry < Integer , HashSet < String > > it : sorted_subsequence . entrySet ( ) ) { System . out . println ( " Subsequences ▁ of ▁ length ▁ = ▁ " + it . getKey ( ) + " ▁ are : " ) ; for ( String ii : it . getValue ( ) ) System . out . print ( ii + " ▁ " ) ; System . out . println ( ) ; } } public static void main ( String [ ] args ) { String s = " aabc " ; possibleSubsequences ( s ) ; } }