426. Сумма

Не решаласьСредняя

Вам дано целое положительное число N N . Найдите все способы, которым это число можно получить, складывая целые положительные числа.

Для того, чтобы не выводить одинаковые способы много раз, суммы должны обладать следующими свойствами:

  • Слагаемые в рамках одного выражения идут в невозрастающем порядке.
  • Выражения перечисляются в лексикографическом порядке. Иначе говоря, для любой пары выражений верно, что раньше будет выписано то из них, в котором меньше число на первой несовпадающей позиции. Например, 2 + 1 + 1 должно быть выписано раньше, чем 2 + 2.

Формат ввода

Во входном файле находится единственное число N N ( 1 ⩽ N ⩽ 40 1 \leqslant N \leqslant 40 ).

Формат вывода

В выходной файл выведите искомые способы получить число N N , по одному способу на строку. Каждое выражение должно состоять из целых положительных чисел, разделенных знаком +, окруженным пробелами.

Ограничения

Ограничение времени
2 с
Ограничение памяти
64 МБ

Примеры

Пример 1

Ввод
4
Вывод
1 + 1 + 1 + 1 
2 + 1 + 1 
2 + 2 
3 + 1 
4 

Теги

18.1.8
Нужно войти, чтобы отправить решение.Войти