suma w 'n' elementowym ciągu

W jaki sposób mogę sprawdzić czy posiadając n elementowy ciąg liczb mogę posumować liczy w taki sposób aby otrzymać dalą liczbę K? np:
ciąg: 1 2 3 4 5
K = 5
Więc mogę wziąć tylko 5 lub 2+3 i tak dalej.

Problem zbliżony dość mocno do problemu złodzieja rabującego sklep. Poczytaj.

Chodzi o sumę dwóch liczb czy o sumę n liczb (n >= 2)?

Naiwne rozwiązanie w C++:
http://ideone.com/5owtwp

można je odrobine przyspieszyć jakby posortować na wejściu liczby i później wyszukiwać binarnie ostatnią liczbę w sumie.

A czy te liczby muszą być po kolei w ciągu wejściowym (tworzyć podciąg)?
Jeżeli tak, to zadania ma proste rozwiązanie O(n), jeżeli nie, to jest problem plecakowy.

No to programowanie dynamiczne o złożoności pamięciowej O(K) oraz złożoności obliczeniowej O(N*K), N-ilość liczb.

W sensie robisz najpierw tablicę k+1-elementową samych zer. Jak przychodzi ci jakaś liczba z wejścia (nazwijmy ją x) to robisz tak:

for(int i=k-x; i>=0; i--)
   if(tab[i])
tab[i+x]=1;

tab[x]=1;

Musisz jeszcze tylko pouwzględniać wychodzenie poza tablicę (w sensie jak masz x=k-1, oraz tab[k-2]=1).

http://pl.wikipedia.org/wiki/Problem_plecakowy (część Rozwiązania dynamiczne)

Algorytm z głowy:

1. posortuj listę liczb
2. ustal WK = K
3. wyszukaj największą tab[i] <= WK
4. jesli nie znaleziono - koniec, brak rozwiazania dla sciezki
5. jesli tab[i] = WK to znalazłeś wynik, wypisz WK i powrót
6. inaczej, wywołaj rekurencyjnie od (3) z WK = WK - tab[i]

Sortowanie jest tylko potrzebne żeby przyspieszyć (3). Można pominąć.