Se citesc n numere naturale si o suma S. Determinati, folosind Programarea Dinamica, daca exista o submultime a celor n numere a carei suma este 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 DA daca exista o astfel de submultime, respectiv NU in caz contrar.
- Restrictii
- 1 <= n <= 500, 0 <= S <= 100000, 0 <= element <= 100000
Exemple
Exemplul 1
Intrare
6 9 3 34 4 12 5 2
Iesire
DA
Exemplul 2
Intrare
5 3 1 2 3 7 8
Iesire
DA