Cho số nguyên dương n. Một cách phân tích n là cách viết n thành tổng của một hoặc nhiều số nguyên dương, không phân biệt thứ tự các số hạng. Quy ước viết các số hạng theo thứ tự không tăng (giảm dần hoặc bằng) để mỗi cách chỉ xuất hiện một lần.
Ví dụ với n=4 có 5 cách: 4, 3 1, 2 2, 2 1 1, 1 1 1 1.
Hãy in ra tất cả các cách phân tích, mỗi cách trên một dòng, các số hạng cách nhau bởi dấu cách. Thứ tự các dòng phải theo quy tắc: cách có số hạng đầu lớn hơn in trước; nếu số hạng đầu bằng nhau thì so sánh các số hạng tiếp theo tương tự (tức thứ tự từ điển giảm dần trên dãy số hạng). Hãy dùng quay lui.
Một dòng chứa số nguyên dương n.
1≤n≤50 (số cách phân tích của 50 là 204226, vẫn in được nhanh).
In ra mỗi cách phân tích trên một dòng theo thứ tự mô tả ở trên.
Ví dụ:
Đầu vào:
4
Đầu ra:
4
3 1
2 2
2 1 1
1 1 1 1
Giải thích:
Đang tải editor...