#include "stdio.h"
#include "conio.h"
#include "iostream.h"
#include "stdlib.h"



int adauga_p(int n)
{
	n=n*10;
	n=n+4;
	return n;
}




int imparte(int n)
{
	n=n/2;
	return n;
}




int adauga_z(int n)
{
	n=n*10;
	return n;
}




int evalueaza_numar(int nr_elemente, int x[])
{
	int numar=4;
	for(int i=0;i<nr_elemente;i++)
	{
		if(x[i]==1)
			numar=adauga_p(numar);
		if(x[i]==2)
			numar=imparte(numar);
		if(x[i]==3)
			numar=adauga_z(numar);
	}
	return numar;
}




bool PotContinua(int k, int x[], int nr_cautat)
{
	if(evalueaza_numar(k,x)<nr_cautat*10)
		return true;
	return false;
}



void backtracking(int x[], int nr_cautat)
{
	int k;
	int cont;
	int nr_sol=0;

	k=0;
	x[k]=0;
	while(k>=0)
	{
		cont=0;
		while(cont==0 && x[k]<3 && k<10)
		{
			x[k]++;
			if(PotContinua(k,x,nr_cautat))
				cont=1;
		}
		if(cont==0)
			k--;
		else
			if(evalueaza_numar(k,x)==nr_cautat)
			{
				nr_sol++;
				cout<<"\nSolutia numarul "<<nr_sol<<" -> ";
				for(int i=0;i<k;i++)
					cout<<x[i]<<"  ";
			//	exit(0);
			}
			else
			{
				k++;
				x[k]=0;
			}
	}
}


void main()
{
	int nr_cautat;
	int x[20];
	
	cout<<"Introduceti numarul : ";
	cin>>nr_cautat;
	backtracking(x,nr_cautat);

}