За решаването на задачата въвеждаме целевата функция F( s , k ), която ни дава броя на начините за получаване на сумата S, и чрез която можем да проверим дали дадена сума S може да се получи при използването на  първите k монети: c0, c1,.....c k-1. В приложената реализация не можем да подходим директно към целта, тъй като конфигурациите нямат явна наредба, но лесно можем да въведем такава, ако изискаме монетите  да бъдат наредени по големина в нарастващ ред. За задачата са в сила  няколко общи случая :
               1.  F( s , k ) = 1+ F( s-c k , k-1 ) + F( s , j ), j = max[cu<c k]   l:c 1 = s;  В този случай формулата от говаря на случая когато съществува монета със стойност S.
                2. F( s , k ) =  F( s-ck , k-1 ) + F( s , j ), j = max[cu<c k]  иначе;  Формулата отговаря на общия случай, когато не същестува  монета със стойност S. Имаме две взаимноизкючващи се възможности:
                        1) k - тата монета учасва в сумата. Броят на тези конфигурации се дава от първото събираемо.    
                        2) k - тата монета не учасва в сумата. Броят на тези конфигурации се дава от второто събираемо.    
       

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

#define MAXCOINS  1000                                                                          
#define MAXSUM 1000   

ifstream fin("file.inp",ios::in);                                                         
ofstream fout("file.out",ios::out);  
unsigned long F[MAXSUM][MAXSUM];    /*Целева функция*/
unsigned coins[MAXCOINS];
unsigned sum;
unsigned n;

int compare(const void *, const void *);        /*qsort( ) Сортира монетите в нарастващ ред */
void init(void);                                               /*Инициализираща функция */         
unsigned long count(int , int );                        /*Проверява дали дадена сума S може да се получи*/

int main(){
    while(fin >>sum >>n){
        for(int i=0; i<n; i++)
            fin >>coins[i];
    }
    init();
    qsort( coins,n,sizeof(int), compare);
    if(!count(sum,n-1))fout<<"No" <<endl;
    system("PAUSE");
    return 0;
}
int compare(const void *i, const void *j){
    return *(int *)i - *(int *)j;
}
void init(void){
   / * Нулиране на целевата функция*/
    unsigned i,j;
    for( i=0;  i<=sum; i++)
        for(j=0; j<=sum; j++)
            F[i][j]=0;
}
unsigned long count(int sum, int k){
    unsigned j;
    if(sum <=0 || k < 0)return 0;
    if(F[sum][k]>0) return F[sum][k];
    else{
        if(coins[k]==(unsigned)sum){
           F[sum][k] = 1;
            fout <<"Yes" <<endl;
            exit(1);
        }
        F[sum][k]+=count(sum-coins[k], k-1);
        j = k;
        while(coins[j]==coins[k])j--;
        F[sum][k]+=count(sum,j);
    }
    return F[sum][k];
}