Sesja

Pewnego dnia, Kasia poszła do sklepu, aby kupić sobie lody. Kiedy dotarła do kasy, okazało się, że nie ma przy sobie drobnych. Sprzedawca powiedział, że może wypłacić jej 10 złotych, ale tylko w monetach o nominałach 1 zł, 2 zł, i 5 zł. Kasia zaczęła się zastanawiać, na ile sposobów można wypłacić 10 złotych. Postanowiła napisać program, który wyświetli wszystkie możliwe kombinacje monet, które można użyć do wypłacenia podanej kwoty w złotych będącej liczbą całkowitą.

Wejście

W pierwszym wierszu podajemy liczbę powtórzeń serii danych m < 50; zakończoną znakiem nowej linii. W osobnych wierszach podajemy należne kwoty pieniędzy w zł, wszystkie mniejsze od 50zł.

Wyjście:

Na wyjściu dostajemy w osobnych wierszach, po spacji, wszystkie różne sposoby wydania odpowiedniej na wejściu kwoty w za pomocą monet 1zł, 2zł, 5zł zaczynając od najmniejszych i zakończone znakiem nowej linii.

Przyklad
Wejście:
3
3
4
5
Wyjscie:
1 1 1
1 2
1 1 1 1 
1 1 2
2 2
1 1 1 1 1 
1 1 1 2
1 2 2
5

Wskazówka:
Rekurencja
Zastanów się najpierw nad liczbą wszystkich sposobów.
Załóżmy, że f(x) to funkcja, która zwraca liczbę wszystkich kombinacji wydania kwoty 10zł. Jeśli wydamy 2zł, to pozostanie nam do wydania 8zł, jeśli teraz wydamy 5zł, to zostanie 3zł  itd. Całą kwotę wydamy, gdy dojdziemy do 0 i funkcja wtedy powinna zwrócić 1 (sposób) lub 0, gdy nie można wydać tej kwoty. Liczba wszystkich sposobów jest równa rekurencji:
f(x)= f(x-1)+f(x-2)+f(x-5)
1, x=0
0, x<0

np. f(4)=?
Zaczynamy liczyć od końca:
f(1)=f(0)+f(-1)+f(-4)=1+0+0=1
f(2)=f(1)+f(0)+f(-3)=1+1+0=2
f(3)=f(2)+f(1)+f(-2)=2+1+0=3
f(4)=f(3)+f(2)+f(-1)=3+2+0=5.
To są wszystkie możliwe wariacje, ale w naszym zadaniu mamy kombinacje!, bo [1 2],to jest to samo co [2 1]. Dlatego powinniśmy pilnować przy dodawaniu nowego elementu na koniec listy (monety), że jest większy bądź równy od ostatniego elementu listy np. do listy[1, 1] możemy dodać monetę 2,bo jest większa od ostatniego elementu listy równego 1 i mamy [1, 1, 2], ale do listy [1, 2] nie dodamy 1, bo ostatni element tej listy to 2. Ogólnie, gdy dodajemy do listy nową monetę, to sprawdzamy czy jest większa lub równa od ostatniego elementu listy, odrzucając w ten sposób wszystkie symetryczne sposoby.