UniLecs #130. Разбиение числа
UniLecs
Задача: давайте вспомним одну из популярных задач на вывод всех разбиений числа N.
Разбиения числа N на слагаемые — это набор целых положительных чисел, сумма которых равна N. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми.
Необходимо вывести всевозможные разбиения N.
Условие: слагаемые в разбиениях должны идти в убывающем порядке.
Входные данные: N - натуральное число от 1 до 30.
Вывод: всевозможные разбиения числа N
Пример: N = 3
Answer:
1 + 1 + 1
2 + 1
3
Идея: воспользуемся рекурсией для упрощения, т.е. для разбивки числа N = n1 + n2 + ... nk (плюс учитываем условие про убывающие слагаемые) берем первое слагаемое n1 и теперь нам нужно разбить число N - n1, для ктр слагаемые будут меньше n1. Детали реализации смотрите в коде.
Реализация:
https://gist.github.com/unilecs/d0d61eef6fdf8e04e93989a41935c101
Test: