정사각형 배치를 사전식 순서로 나열하기

같은 크기의 정사각형 종이가 $n$개 있다. 이 종이들의 아랫변을 수평으로 맞춰 여러 개의 열로 나란히 세운다. 단, 서로 이웃한 두 열은 왼쪽 열의 높이가 오른쪽 열의 높이보다 낮아지지 않도록(즉 왼쪽에서 오른쪽으로 갈수록 높이가 같거나 낮아지도록) 배치해야 한다. 예를 들어 $n = 5$일 때는 다음과 같이 7가지 배치가 가능하다.

각 배치는 왼쪽 열부터 차례로 그 열에 쌓인 정사각형의 개수를 나열한 수열로 나타낸다. 예를 들어 $n = 5$일 때 위의 7가지는 각각

$(5)\quad (4, 1)\quad (3, 2)\quad (3, 1, 1)\quad (2, 2, 1)\quad (2, 1, 1, 1)\quad (1, 1, 1, 1, 1)$

로 표현된다.

$n$이 주어졌을 때 가능한 모든 배치를 사전식 순서로 출력하는 프로그램을 작성하여라. $n \le 30$이다. 여기서 사전식 순서란, 두 배치 $(a_1, a_2, \ldots, a_s)$와 $(b_1, b_2, \ldots, b_t)$에 대해 $a_1 > b_1$이거나, 어떤 정수 $i > 1$이 존재하여 $a_1 = b_1, \ldots, a_{i-1} = b_{i-1}$이고 $a_i > b_i$가 성립할 때 $(a_1, a_2, \ldots, a_s)$를 $(b_1, b_2, \ldots, b_t)$보다 먼저 출력하도록 정한 순서를 말한다.

첫째 줄에 정수 $n$이 주어진다.

가능한 모든 배치를 사전식 순서로 한 줄에 하나씩 출력하고, 마지막에 개행 문자를 넣는다. 배치 $(a_1, a_2, \ldots, a_s)$는 정수 $a_1, a_2, \ldots, a_s$를 이 순서대로 공백 하나로 구분하여 출력한다.