問題3

同じ大きさの正方形の紙が n 枚ある．これらの紙の下部を水平に揃えて何列 かに並べる．ただし，隣り合う列は左側が右側より低くならないように並べなけれ ばならない．例えば, n = 5 のときは，次のような 7 通りの並べ方が可能である．

これらを，各列に並んだ正方形の個数の列で表すことにする．例えば，n = 5 の ときは，それぞれ，

(5) (4, 1) (3, 2) (3, 1, 1) (2, 2, 1) (2, 1, 1, 1) (1, 1, 1, 1, 1)

と表わされる．

n を入力したとき， 辞書式順序で全て出力するプログラムを作成せよ．n ≤ 30 とする．ただし, 辞書式順序とは２つの並べ方 (a1, a2, ..., as) が並べ方 (b1, b2, ..., bt) に対して, a1 > b1 または, ある整数 i > 1 が存在して a1 = b1, ..., ai−1 = bi−1 かつ ai > bi が成り立つとき (a1, a2, ..., as) が (b1, b2, ..., bt) より先に出力されるように並 べることである.

1 行からなり, 1 行目に n が書かれている．

辞書式順序で1 行に１通りずつ書き最後に改行を入れること. 並べ方は (a1, a2, ..., as) の出力は整数 a1, a2, . . . , as をこの順番に空白で区切って出力すること.