Suma cifrelor s backtracking

Sa se afiseze toat numerele formate din cifre distincte cu proprietatea ca suma cifrelor este s, unde s se citeste de la tastatura.

Sa se folosesca metoda backtracking.

#include<iostream.h>
#include<conio.h>
int st[20],n,k,s,c;

void init(int k)
{st[k]=-1;}

int succesor(int k)
{if((st[k]<9)&&(st[k]<s))
{st[k]++;
return 1;
}
else return 0;}

int valid(int k)
{int suma=0;
for(int i=1;i<k;i++)
if(st[k]==st[i]) return 0;
for(i=1;i<=k;i++) suma=suma+st[i];
if(suma>s) return 0;
if((k==1)&&(st[k]==0)) return 0;
return 1;}

int sol(int k)
{int suma=0;
for(int i=1;i<=k;i++)suma=suma+st[i];
return(suma==s);}

void tipar(int k)
{
//c++;cout<<“solutia”<<c<<“: “;
for(int i=1;i<=k;i++) cout<<st[i];
cout<<endl;
//if(c%20==0) {cout<<“enter”;getch();}
}

void bkt()
{int as,k=1;
init(k);
while(k>0)
{
do{} while((as=succesor(k)) && !valid(k));
if (as) {
if(sol(k)) tipar(k);
if(st[k]!=0) {k++;init(k);}
else {k++;init(k);}
}
else k–;
}
}

void main()
{cout<<“s=”;cin>>s;
//c=0;
bkt();
getch();
}