文字列のすべての順列を出力する

あなたはある文字列を与えられ、その文字列の文字を組み合わせたすべての順列を生成し、出力する再帰関数を作成するよう求められています。文字列の順列とは、その文字を並べ替えたものと定義されます。

入力の唯一の行には、文字列 s が含まれています。

プログラムの出力は、文字列 s の文字を使ったすべての順列であるべきです。各順列は新しい行に出力してください。順列の順序は問いません。