Podział liczby na sumy.

Witam. Mam zadanie, aby napisać program w języku C++, który będzie wypisywał dla dowolnej liczby podział na wszystkie możliwe sumy (z kolejnymi liczbami ułożonymi niemalejąco). Na przykład, dla liczby 5 wypisze on kolejne linijki:
5=5
5=1+4
5=1+1+3
5=1+1+1+2
5=1+1+1+1+1
5=1+2+2
5=2+3
Program ma być napisany rekurencyjnie. Nie mam pojęcia jak się w ogóle za to zabrać, każda próba jest dość daleka od wyniku który mam otrzymać.

n = 1 + (n-1) = 2 + (n-2) = 1 + (2 -1) [! Tutaj rekurencja] + (n-2)

Jakos tak chyba

https://www.geeksforgeeks.org/find-all-combinations-that-adds-upto-given-number-2/

Ja to bym zrobił tak (pseudokod, specjalnie nie c/c++, żebyś jednak się wysilił):

function sums(num)
    prefix = Array[ ]
    sums_recursion(prefix, num)

function sums_recursion(prefix, num)
    print(prefix, num)
    maxx = floor(num / 2)
    minx = 1
    if prefix not empty
        minx = last_element(prefix)
    for x in [minx..maxx]
        prefix.push(x)
        sums_recursion(prefix, num - x)
        prefix.pop()

Tzn:

• Podzieliłbym rozkład sumy na prefiks i n.
• Budowałbym rekurencyjnie, dodając na kolejnych poziomach rekurencji liczbę do prefiksu sumy.
• Prefiks jest posortowany nie-malejąco na każdym poziomie rekurencji.
• Liczba n jest większa lub równa od ostatniego elementu z prefiksu.