Phân tích số

Nhà toán học trẻ Alice muốn tìm tất cả các cách để phân tích một số nguyên dương \(N\) thành tổng của các số nguyên dương không vượt quá N. Ví dụ, \(4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1\). Hãy sử dụng đệ quy để đếm và liệt kê các cách phân tích này.

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 30\)).

Output

Dòng đầu tiên in ra số lượng cách phân tích. Các dòng tiếp theo in ra từng cách phân tích, trong đó các số hạng được sắp xếp giảm dần và mỗi cách phân tích được in theo thứ tự từ điển.

Example

Test 1

Input

Output

1
So luong cach phan tich: 1

Test 2

Input

Output

1+1
2
So luong cach phan tich: 2

Test 3

Input

Output

1+1+1
2+1
3
So luong cach phan tich: 3

Test 4

Input

Output

1+1+1+1
2+1+1
2+2
3+1
4
So luong cach phan tich: 5

Thông tin bài

Điểm:

100

Thời gian:

1.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

02/08/2026

Tác giả:

root

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận