text: Generate all binary strings without consecutive 1 's | A utility function generate all string without consecutive 1 'sof size K ; print binary string without consecutive 1 's ; terminate binary string ; if previous character is '1' then we put only 0 at end of string example str = "01" then new string be "000" ; if previous character is '0' than we put both '1' and '0' at end of string example str = "00" then new string "001" and "000" ; function generate all binary string without consecutive 1 's ; Base case ; One by one stores every binary string of length K ; Generate all Binary string starts with '0 ; Generate all Binary string starts with '1 ; Driver code
code: def generateAllStringsUtil ( K , str , n ) : NEW_LINE INDENT if ( n == K ) : NEW_LINE INDENT print ( * str [ : n ] , sep = " " , end = " ▁ " ) NEW_LINE return NEW_LINE DEDENT if ( str [ n - 1 ] == '1' ) : NEW_LINE INDENT str [ n ] = '0' NEW_LINE generateAllStringsUtil ( K , str , n + 1 ) NEW_LINE DEDENT if ( str [ n - 1 ] == '0' ) : NEW_LINE INDENT str [ n ] = '0' NEW_LINE generateAllStringsUtil ( K , str , n + 1 ) NEW_LINE str [ n ] = '1' NEW_LINE generateAllStringsUtil ( K , str , n + 1 ) NEW_LINE DEDENT DEDENT def generateAllStrings ( K ) : NEW_LINE INDENT if ( K <= 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT str = [ 0 ] * K NEW_LINE DEDENT ' NEW_LINE INDENT str [ 0 ] = '0' NEW_LINE generateAllStringsUtil ( K , str , 1 ) NEW_LINE DEDENT ' NEW_LINE INDENT str [ 0 ] = '1' NEW_LINE generateAllStringsUtil ( K , str , 1 ) NEW_LINE DEDENT K = 3 NEW_LINE generateAllStrings ( K ) NEW_LINE