Backtracking recursiv

In cazul variantei recursive rutina back se defineste ca o functie recursiva cu parametrul k (nivelul curent din stiva). Urcarea in stiva se face prin autoapelul functiei back cu o noua valoare pentru k. Generarea potentialilor candidati la solutie se face print-o instructiune for care parcurge valorile posibile de la limita inferioara la limita superioara. Iata solutia pentru problema permutarilor.

#include<iostream.h>

#include<conio.h>

int st[20],n;

void tipar()

{for(int i=1;i<=n;i++)

cout<<st[i]<<' ';

cout<<endl;}

int valid(int k)

{ for(int i=1;i<=k-1;i++)

if (st[i]==st[k])

return 0;

return 1;}

void back(int k)

{for(int i=1;i<=n;i++)

{st[k]=i;

if (valid(k))

if(k==n)

tipar();

else

back(k+1);

}

}

void main()

{clrscr();

cout<<"n=";

cin>>n;

back(1);

getch();

}