Описание задачи
Найти количество способов разложить число n на сумму натуральных слагаемых, используя не
более c слагаемых. Опционально — вывести все разложения.
Режимы работы
# n c— только посчитать количество разложений? n c— вывести все разложения и их количество
При невалидном вводе (нечисловые значения, отрицательные числа) — Invalid input.
Формат выходных данных
Для режима #:
Total: K
Для режима ?:
=a+b+c
=d+e
Total: K
Примеры
Невалидный ввод
# ab 2 Invalid input.
Только количество
# 6 6 Total: 10
С перечислением
? 5 3 =2+2+1 =3+2 =3+1+1 =4+1 Total: 4
Ключевые моменты
- Классическая задача на разбиение числа (partition problem)
- Рекурсия с мемоизацией или динамическое программирование
- Слагаемые упорядочены по убыванию (избежать дубликатов)