//4. Cunoscand valorile a n monede, precum si numarul de exemplare din fiecare moneda,
// sa se plateasca o suma de bani s doar cu monedele avute la dispozitie.

#include <fstream>
using namespace std;
fstream f("date.in",ios::in);
fstream g("date.out",ios::out);
int x[20], n, nrsol=0, nr[20], val[20], sum[20], S;
void Afisare()
{
	int i;
	g<<S<<"=";
	for(i=1;i<=n;i++)
	   if (x[i]!=0) 
		   g<<x[i]<<"*"<<val[i]<<" lei + ";
	g<<endl;
}
int Valid(int k)
{
	sum[k]=sum[k-1]+val[k]*x[k];
	if (sum[k]>S) 
		return 0;
	if (k==n && sum[k]!=S) 
		return 0;
	return 1;
}
void Back()
{
	int k=1, cand;
	x[1]=-1;
	while (k>0)
    {
		cand=0;
		 while (cand==0 && x[k]<nr[k])
		  {
			  x[k]++;
		   cand=Valid(k);
		  }
		 if (cand==0) 
			 k--;
		 else if (k==n) 
			 Afisare();
		else 
		{
			k=k+1; 
			x[k]=-1;
		}
    }
}
int main()
{
	int i;
	f>>n;//numarul de tipuri de monezi
	f>>S;
	for (i=1;i<=n;i++)
    {
		 f>>val[i];//valoarea monedei i
		 f>>nr[i];//numarul de monezi i
    }
	Back();
	return 0;
}




Alta rezolvare:

#include <iostream>
using namespace std;
int monezi[10],cantitate[10],n,suma;
void citire(int v[])
{
for (int i=1;i<=n;i++)
cin>>v[i];
}
int solutie[10];
void afisare()
{
cout<<suma<<"=";
for(int i=1;i<=n;i++)
{
cout<<monezi[i]<<"*"<<solutie[i];
if(i<n)
cout<<"+";
}
cout<<endl;
}

bool valid(int k)
{
int s=0;
for (int i=1;i<=n;i++)
s=s+monezi[i]*solutie[i];
if (s==suma)
return 1;
else
return 0;
}
void back(int k)
{
if (k==n)
return;
for (int j=0;j<=n;j++)
{
for (int i=0;i<=cantitate[j];i++)
{
solutie[j]=i;
if (valid(k))
afisare();
back(k+1);
}
}
}
int main()
{
cout<<"Cate monezi aveti? ";
cin>>n;
cout<<"Introduceti suma: ";
cin>>suma;
cout<<"Ce tipuri de monezi aveti? ";
citire(monezi);
cout<<"Ce cantitate din fiecare moneda aveti? ";
citire(cantitate);
back(1);
return 0;
}




2. Problema cu paranteze

#include <iostream>
using namespace std;
int n,v[100];
void afisare()
{
for (int i=1;i<=n;i++)
{
if (v[i])
cout<<"(";
else
cout<<")";
}
cout<<endl;
}
bool valid (int k)
{ 
int pi=0,pd=0;
for (int i=1;i<=n;i++)
{
if (v[i])
pd++;
else
pi++;
if ((pi>pd)||(pd>n/2)||(pi>n/2))
return 0;
}
return 1;
}
void back (int k)
{
for (int i=0;i<=1;i++)
{
if (k==n)
return;
v[k]=i;
if (valid(k))
afisare();
back(k+1);
}
}
int main()
{
cout<<"Introduceti numarul de paranteze:";
cin>>n;
if (n%2==0)
back(1);
else
cout<<"Nu exista secventa de paranteze corect inchise pentru "<<n;
return 0;
}