10/21

Bancnote

#include<iostream>
using namespace std;
int b[100],x[100],nr=0,n;

void afisare(int n)
{int i;
for(i=1;i<=n;i++)
    if(x[i])
        cout<<x[i]<<"*"<<b[i]<<" ";
cout<<endl;
nr++;}

void back(int i,int s)
{int j;
if(i==n)
    {if(s%b[i]==0)
        {x[i]=s/b[i];
        afisare(i);}
    }
    else{
        for(j=0;j<=s/b[i];j++)
            {x[i]=j;
            if(s==j*b[i])
                afisare(i);
            else back(i+1,s-j*b[i]);
            }
        }
    }


int main()
{int i,j,s;
cin>>s>>n;
for(i=1;i<=n;i++)
    cin>>b[i];
back(1,s);
cout<<endl<<nr<<" solutii";
}