Se citesc n numere naturale si o suma S. Determinati, folosind Programarea Dinamica, cate submultimi (alese dupa pozitie, nu dupa valoare) ale celor n numere au suma exact S.
- Date de intrare
- Pe prima linie se citesc n si S. Pe a doua linie se citesc cele n numere.
- Date de iesire
- Se afiseaza un singur numar: numarul de submultimi cu suma S.
- Restrictii
- 1 <= n <= 40, 0 <= S <= 10000, 0 <= element <= 10000
Exemple
Exemplul 1
Intrare
6 9 3 34 4 12 5 2
Iesire
2
Exemplul 2
Intrare
5 10 1 2 3 4 5
Iesire
3