Se citesc un numar natural m, cele m valori distincte ale unor monede disponibile in cantitate nelimitata, si o suma S. Generati, folosind metoda Backtracking, toate modurile de a obtine suma S folosind aceste monede (fiecare moneda putand fi folosita de oricate ori).
- Date de intrare
- Pe prima linie se citeste m. Pe a doua linie se citesc cele m valori ale monedelor. Pe a treia linie se citeste S.
- Date de iesire
- Se afiseaza toate modurile de a obtine suma S, cate unul pe linie, sub forma 'valoare1:cantitate1 valoare2:cantitate2 ... valoarem:cantitatem' (in ordinea monedelor citite), in ordinea generata de backtracking (numarul de monede de prima valoare crescand de la 0).
- Restrictii
- 1 <= m <= 4, 1 <= valoare moneda <= 30, 0 <= S <= 30
Exemple
Exemplul 1
Intrare
2 1 2 4
Iesire
1:0 2:2 1:2 2:1 1:4 2:0
Exemplul 2
Intrare
3 1 2 5 5
Iesire
1:0 2:0 5:1 1:1 2:2 5:0 1:3 2:1 5:0 1:5 2:0 5:0