Subarray / Substring vs Subsequence and Programs to Generate them | Java code to generate all possible subsequences . Time Complexity O ( n * 2 ^ n ) ; Number of subsequences is ( 2 * * n - 1 ) ; Run from counter 000. . 1 to 111. . 1 ; Check if jth bit in the counter is set If set then print jth element from arr [ ] ; Driver method to test the above function
import java . math . BigInteger ; class Test { static int arr [ ] = new int [ ] { 1 , 2 , 3 , 4 } ; static void printSubsequences ( int n ) { int opsize = ( int ) Math . pow ( 2 , n ) ; for ( int counter = 1 ; counter < opsize ; counter ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( BigInteger . valueOf ( counter ) . testBit ( j ) ) System . out . print ( arr [ j ] + " ▁ " ) ; } System . out . println ( ) ; } } public static void main ( String [ ] args ) { System . out . println ( " All ▁ Non - empty ▁ Subsequences " ) ; printSubsequences ( arr . length ) ; } }