Se citesc un numar natural n, cele n numere naturale nenule ale unui vector, si un numar natural S. Generati, folosind metoda Backtracking (schema include/exclude), toate submultimile vectorului a caror suma este exact S.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n numere. Pe a treia linie se citeste S.
- Date de iesire
- Se afiseaza toate submultimile cu suma S, cate una pe linie, cu elementele separate prin spatiu, in ordinea generata de schema include/exclude (exclude inaintea includerii, pentru fiecare element in ordinea data). Daca S=0, se afiseaza o linie goala (multimea vida).
- Restrictii
- 1 <= n <= 15, 1 <= v[i] <= 1000, 0 <= S <= 15000
Exemple
Exemplul 1
Intrare
3 1 2 3 3
Iesire
3 1 2
Exemplul 2
Intrare
4 1 2 3 4 5
Iesire
2 3 1 4