Разбор добавил Евгений Казаков
В данной задаче нужно применять рекурсию.
О том, что это такое можно почитать вот здесь https://ru.wikipedia.org/wiki/Рекурсия
Если кратко и в отношении программирования, то рекурсия - это функция, которая при выполнении вызывает сама себя.
Решение задачи следующее:
Давайте заметим, как именно формируется наш ответ на исходном примере:
5:
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5
Перебирается число 1..N(1..5 в данном случае), которое будет на первом месте в разложении, назовем это число P.
На второе место мы можем поставить число <= P (т. к. по условию задачи, все разложения не должны возрастать).
Его мы также перебираем и идем дальше перебирать третье число в разложении, затем четвертое и т. д.
После того, как мы дошли до момента, когда сумма всех чисел текущего разложения равна исходному числу N,
мы выводим это разложение и возвращаемся назад.
Этот алгоритм повторяется, пока не переберутся все первые числа.
Пример, для пятерки:
1. Ставим на первое место 1. Дальнейшие элементы все равны 1.
2. Ставим на первое место 2. На второе место мы можем поставить 1, тогда дальше пойдут только единицы.
Или можем поставить 2, тогда на третьем месте будет 1, т. к. дальше мы перебирать не сможем.
3. Ставим на первое место 3. На второе можем поставить 1, тогда на третьем тоже будет 1.
Или 2, тогда дольше ничего не будет.
4. Ставим на первое место 4. На второе мы можем поставить только 1.
5. Ставим на первое место 5. Дальше продолжить это разложение не можем.
Давайте напишем рекурсивную функцию, которая на вход будет принимать число X - число, которое необходимо донабрать в текущем разложении
и число P - максимально возможный элемент, который мы можем поставить на текущем шаге.
В ней, если X = 0, мы выводим все текущее разложение и завершаем работу функции, т. к. дальше перебирать его мы не можем.
Если X > 0, то перебираем число Q[1..P], которое мы можем поставить на текущем шаге, и снова вызываем функцию с параметрами (X - Q, Q).