[C/C++]Liczba na wszystkie sposoby dodawania

[Wojtek94]

Witam!

Potrzebuję wskazówki do algorytmu. Podaję liczbę 'n' i program podaje mi wszystkie możliwe sposoby jej uzyskania za pomocą dodawania wszystkich liczb naturalnych dodatnich.
Przykład:
Wejście:
3
Wyjście:
3
1+2
1+1+1
Jak widać przemienność dodawania pomijamy. Kiedyś widziałem przydatne do tego informacje po długim googlowaniu, ale teraz nie mogę tego znaleźć

Pozdrawiam.

[kabanek]

możesz spróbować zrobić tak, że będziesz powoli rozbijać kolejną liczbę na mniejsze
czyli np dla 4:
4 = 3 + 1 = (2 + 1) + 1 = ((1 + 1) + 1) + 1

[Wojtek94]

Takim sposobem pominę 2+2 zdaje się?

[sylweeczek]

Jak masz n to zmniejszasz ją w pętli o 1 i za każdym razem wypisuj resztę składników z jakimi to co masz da ci daną liczbę n. hmmm takie masło maślane;/ może zrozumiesz na przykładzie n=4
4
4=3+1
4=2+(2)
4=2+1+1
4=1+(3)
4=1+((2)+1)
4=1+1+1+1
To co masz w nawiasach rozpisujesz podobnie jak 4. To pewnie można i jakoś sprytnie rekurencyjnie rozłożyć ale nie chce mi się teraz myśleć. Tylko mam takie pytanie po co? przy większych liczbach to strasznie zamuli procka?

[Wojtek94]

Zadanko na infe : P
Input jest do 40, więc chyba da rade z takim rozwiązaniem.
Spróbuje coś napisać, ale chętnie też oczekuje nowych, optymalniejszych pomysłów
Dobranoc, pozdrawiam

[kabanek]

Takim sposobem pominę 2+2 zdaje się?

zgadza się algorytm @sylweeczek wydaje się być ok jedna funkcja rekurencyjna załatwi sprawę