Metoda Backtracking

Sa se genereze toate sirurile de lungime n, formate numai din literele A si M, siruri care sa nu aiba doua litere A alaturate.Valoarea numarului natural n se citeste de la tastatura. Pentru n=3, se vor afisa sirurile: MMM, AMM, MAM, MMA,AMA.

#include<iostream.h>
int n,k,i;
char a[3],st[20];
int valid(int k)
{
for(i=1;i<k;i++)
if(k>1&&st[k]=='A'&&st[k-1]=='A')
return 0;
return 1;}
int sol(int k)
{ return (k==n);}
void tipar(int k)
{for(i=1;i<=k;i++)
cout<<st[i]<< " ";
cout<<endl;}
void bkt(int k)
{int val;
for(val=1;val<=2;val++)
{st[k]=a[val];
if(valid(k))
if(sol(k))	 
tipar(k);
else
bkt(k+1);
}}
void main()
{
cin>>n;
a[1]='A';
a[2]='M';
bkt(1);}