Третият вариант на задачата е реализиран чрез итеративен алгоритъм. Сумата на всички монети S може да бъде изчислена линейно,  т.е. с единствено преминаване през монетите. Още в началото на програмата, по време на въвеждането на входните данни се извършва сумиране на монетите в променливата s_coins. Също и ще поддържаме булев масив can, за който can[i] = true тогава и само тогава, когато сумата  can може да бъде получена  с помощта на монетите. Ако имаме зададена сума 0 за нея ще считаме, че тя може да бъде получена без да се използва нито една монета. Всички останали суми ще се получават с използване на поне една монета.

    Нека в масива can са отбелязани всички възможни суми с използване на първите k монети. Тогава сумите, които могат да бъдат получени с прибавяне на ( k+1 ) - вата монета, се получават като към всяка от сумите в can прибавим стойността на ( k+1) - вата монета. Това може да се извърши чрез еднократно обхождане на елементите на can, като за всяко i, can[i] = true установяваме в true и can[i + S(k+1)]. Посоката на обхождане е съществена. Ако разглеждаме елементите на can по нарастване на индексите им, възникват нежелани ситуации, при които един и същи елемент се включва в сумата неколкократно, което е недопустимо. Така, след като сме установили в true  can[i + S(k+1)], при  по - нататъшното разглеждане на can ще установим в true и can[i+S(k+1)+S(k+1)]. В случай, че can[i + S(k+1)] не е било true преди началото началото на обхождането, последното установяване в true ще бъде некоректно, тъй като ( k+1)-вият елемент ще се окаже включен в сумата два пъти. Бихме могли да направим една оптимизация - след намирането на всяка сума в масива can, да проверяваме дали can[S] = true,  а именно да прекратим изпълнението на алгоритъма при първото установяване на  can[S] в true. Подобрението не се отразява съществено на ефективността на алгоритъма, най - малкото защото в случай, че сумата S  не може да бъде получена, се налага пълното изпълнение на алгоритъма.


#include <cstdlib>                                                                                            
#include <fstream>
#include <cstring>                                                                                                                                    
#include <iostream>
using namespace std;

#define MAXCOINS  1000                                                                          
#define MAXSUM 1000   
  
unsigned coins[MAXCOINS];
bool can[MAXSUM];
unsigned sum;
unsigned n;
unsigned s_coins = 0;


bool Check(){
    memset(can,MAXSUM,false);
    can[0]=true;
    for(int i=0; i<=n; i++)
        for(int j=s_coins; j>=0; j--)
            if(can[j])
               if((coins[i]+j)==sum) return true;
               else can[coins[i]+j] = true;
    return false;
}
int main(){

    ifstream fin("file.inp",ios::in);
    ofstream fout("file.out",ios::out);
    while(fin >>sum >>n){
        for(int i=0; i<n; i++){
            fin >>coins[i];
            s_coins+=coins[i];
        }
        if(Check()) fout <<"Yes";
        else fout <<"No";
    }
    system("PAUSE");
    return 0;
}