Paraules compensades X46137

Considereu una paraula s de longitud n, amb només lletres ‘a’ i ‘b’. Per a qualsevol dels seus prefixos p, sigui a(p) el nombre de ‘a’ dins de p, i sigui b(p) el nombre de ‘b’ dins de p. En aquest problema, direm que s està compensada si i només si per a qualsevol dels n+1 prefixos p d’s es compleix | a(p) − b(p) | ≤ 2.

Per exemple, “abbaaabb” està compensada, però “abbaaaab” no ho està, perquè “abbaaaa” n’és un prefix amb cinc ‘a’ i dues ‘b’. Com altres exemples, ni “bbb” ni “bbbbbb” estan compensades.

Donada una n, escriviu totes les paraules compensades d’aquesta longitud.

Entrada

L’entrada consisteix en una n entre 1 i 18.

Sortida

Escriviu en ordre alfabètic totes les paraules compensades amb n caràcters escollits entre ‘a’ i ‘b’.