Mam do napisania program, który sprawdzi czy można z danych odcinków stworzyć (poprzez ich dodawanie) dany odcinek.
Specyfikacja:
Wejście:
Podane są dwie liczby n <= 10000 i k <= 10000, oznaczające kolejno n - długość odcinka który będziemy sprawdzać i k - ilość odcinków, które będziemy podawać. A następnie należy podać k długości odcinków.
Wyjście:
TAK jeżeli da się z podanych odcinków zbudować odcinek o długości n, lub NIE jeżeli nie ma takiej możliwości.
Np dla wejścia:
16 5
10
7
2
8
1
Wyjściem jest TAK, ponieważ odcinek 16 możemy utworzyć sumując odcinki o długościach 7, 8 i 1.
Głowię się z tym już 3 godziny, jakieś propozycje?
Miałem pomysł, aby sumowal kolejne kombinacje odcinkow i sprawdzal czy sa rowne odcinkowi o dlugosci n, ale nie wiem jak to skodzic.
Musze to napisac w C++.