Pujades i baixades X57029

Suposeu un món bidimensional. Una mosca es troba inicialment a la posició $(0, 0)$, i farà $n$ moviments unitaris cap a la dreta, mai baixant sota terra. A cada pas, o bé es quedarà a la mateixa alçada, o bé pujarà una unitat, o bé baixarà una unitat. Genereu totes les possibles trajectòries de la mosca.

Per exemple, aquesta és una trajectòria possible per a $n=11$:

Codifiqueu les trajectòries amb ‘u’ per pujar (up), ‘d’ per baixar (down), i ‘h’ per moure’s horitzontalment. La trajectòria anterior es codifica “uududhdhuud”.

Entrada

L’entrada consisteix en una $n$ entre 1 i 11.

Sortida

Escriviu totes les trajectories possibles en ordre alfabètic.