Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările mulţimii {1,2,..,n}.

#include <fstream>

using namespace std;
ifstream fin("permutari.in");
ofstream fout("permutari.out");
int st[101],n;
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k])
            return 0;
    return 1;
}
void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<st[i]<<" ";
    fout<<endl;
}
void bkt()
{
    int k,ok;
    k=1;
    st[k]=0;
    while(k>0)
    {
        ok=0;
        while(st[k]<n&&!ok)
        {
            st[k]++;
            ok=valid(k);
        }
        if(ok==1)
        {
            if(k==n)
                tipar(k);
            else
                st[++k]=0;
        }
        else
            k--;
    }
}
int main()
{
    fin>>n;
    bkt();
    return 0;
}


Se citeşte un număr natural nenul n. Să se afişeze, în ordine invers lexicografică, permutările mulţimii {1,2,..,n}.
#include <fstream>

using namespace std;
ifstream fin("permutari1.in");
ofstream fout("permutari1.out");
int st[101],n;
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k])
            return 0;
    return 1;
}
void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<st[i]<<" ";
    fout<<endl;
}
void bkt()
{
    int k,ok;
    k=1;
    st[k]=n+1;
    while(k>0)
    {
        ok=0;
        while(st[k]>1&&ok==0)
        {
            st[k]--;
            ok=valid(k);
        }
        if(ok==1)
        {
            if(k==n)
                tipar(k);
            else
                st[++k]=n+1;
        }
        else
            k--;
    }
}
int main()
{
    fin>>n;
    bkt();
    return 0;
}


Se citeşte un număr natural nenul n, apoi n numere naturale distincte. Să se afişeze, în ordine lexicografică, permutările mulţimii formate din cele n numere citite.

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("permutari2.in");
ofstream fout("permutari2.out");
int st[101],n, v[101];
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k])
            return 0;
    return 1;
}
void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<v[st[i]]<<" ";
    fout<<endl;
}
void bkt()
{
    int k,ok;
    k=1;
    st[k]=0;
    while(k>0)
    {
        ok=0;
        while(st[k]<n&&!ok)
        {
            st[k]++;
            ok=valid(k);
        }
        if(ok==1)
        {
            if(k==n)
                tipar(k);
            else
                st[++k]=0;
        }
        else
            k--;
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    sort(v,v+n+1);
    bkt();
    return 0;
}


Se consideră o tablă de șah de dimensiune n. Să se plaseze pe tablă n regine astfel încât să nu existe două regine care să se atace.

#include <iostream>
#include <cmath>

using namespace std;

int n,x[20];
bool gasit;

bool cont(int k)
{
    for(int i=1;i<k;i++)
    {
        if(x[i]==x[k])
            return false ;
        if(k-i==abs(x[k]-x[i]))
            return false;
    }
    return true;
}

void afisare(int n)
{
    gasit=true;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(x[j]==i)
                cout<<"*";
            else
                cout<<"-";
        cout<<'\n';
    }
}


void bkt(int k)
{
    for(int i=1;!gasit && i<=n;i++)
    {
        x[k]=i;
        if(cont(k))
            if(k==n)
                afisare(n);
            else
                bkt(k+1);
    }
}
int main()
{
    cin>>n;
    bkt(1);
    return 0;
}

Fie mulţimea M={1,2,..,n} şi P(1),P(2),...,P(n) o permutare a ei. Elementul x din M se numeşte punct fix dacă P(x)=x.
Cerinţa

Se citeşte un număr natural nenul n. Să se afişeze, în ordine lexicografică, permutările fără puncte fixe ale mulţimii {1,2,..,n}.

#include <fstream>
using namespace std;

ifstream f("permpf.in");
ofstream g("permpf.out");

int st[100],n;
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k]||st[i]==i||st[k]==k)
            return 0;
    return 1;
}

void tipar(int k)
{
    for(int i=1;i<=k;i++)
        g<<st[i]<<' ';
    g<<'\n';
}

void bkt()
{
    int k=1;
    st[k]=0;
    while(k>0)
    {
        bool ok=0;
        while(st[k]<n&&!ok)
        {
            st[k]++;
            ok=valid(k);
        }
        if(ok)
            if(n==k)
                tipar(k);
            else
                st[++k]=0;
        else
            k--;

    }
}
int main()
{
    f>>n;
    bkt();
    return 0;
}

Se citeşte un număr natural nenul n, apoi n numere naturale distincte. Să se afişeze, în ordine lexicografică, șirurile din cele n valori cu proprietatea că oricare două valori învecinate sunt prime între ele.

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("sirpie.in");
ofstream fout("sirpie.out");
int st[101],n, v[101];
int cmmdc(int a,int b)
{
    int t;
    while(b!=0)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k])
            return 0;
    if(k>1)
    {
        if(cmmdc(v[st[k]],v[st[k-1]])==1)
            return 1;
        else
            return 0;
    }
    return 1;
}
void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<v[st[i]]<<" ";
    fout<<endl;
}
void bkt()
{
    int k,ok;
    k=1;
    st[k]=0;
    while(k>0)
    {
        ok=0;
        while(st[k]<n&&!ok)
        {
            st[k]++;
            ok=valid(k);
        }
        if(ok==1)
        {
            if(k==n)
                tipar(k);
            else
                st[++k]=0;
        }
        else
            k--;
    }
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    sort(v,v+n+1);
    bkt();
    return 0;
}


Se numește anagramă a unui cuvânt dat, un alt cuvânt ce conține toate literele primului, eventual în altă ordine.
Cerinţa

Se dă un cuvânt din cel mult 8 litere distincte. Să se afișeze, în ordine alfabetică, toate anagramele acestui cuvânt.

#include <fstream>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream fin("anagrame1.in");
ofstream fout("anagrame1.out");
int st[101],n;
char v[9];
bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(st[i]==st[k])
            return 0;
    return 1;
}
void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<v[st[i]-1];
    fout<<endl;
}
void bkt()
{
    int k,ok;
    k=1;
    st[k]=0;
    while(k>0)
    {
        ok=0;
        while(st[k]<n&&!ok)
        {
            st[k]++;
            ok=valid(k);
        }
        if(ok==1)
        {
            if(k==n)
                tipar(k);
            else
                st[++k]=0;
        }
        else
            k--;
    }
}
int main()
{
    fin>>v;
    n=strlen(v);
    sort(v,v+n);
    bkt();
    return 0;
}


Se citește un număr natural n (n<16). Afișați în ordine lexicografică toate permutările mulțimii {1,2,…,n} în care elementele pare sunt puncte fixe (nu își schimbă poziția).

#include <iostream>

using namespace std;

int st[20],n;
void tipar()
{
    for(int i=1; i<=n; i++)
        cout<<st[i]<<" ";
    cout<<'\n';
}
bool valid(int k)
{
    if (k%2==0&&st[k]!=k)
        return 0;
    for(int i=1; i<k; i++)
        if(st[i]==st[k])
            return 0;
    return 1;

}
void bkt(int k)
{
    for (int i=1; i<=n; i++)
    {
        st[k]=i;
        if (valid(k))
            if (k==n)
                tipar();
            else
                bkt(k+1);

    }
}
int main()
{
    cin>>n;
    bkt(1);
    return 0;
}

Se citesc două numere naturale nenule n și k. Să se afişeze, în ordine lexicografică, aranjamentele de câte k elemente ale mulţimii {1,2,..,n}.

#include <fstream>

using namespace std;

ifstream fin("aranjamente.in");
ofstream fout("aranjamente.out");

int sol[100],n,p;

bool valid(int k)
{
    for(int i=1;i<k;i++)
        if(sol[i]==sol[k])
            return 0;
    return 1;
}

void tipar(int k)
{
    for(int i=1;i<=k;i++)
        fout<<sol[i]<<" ";
    fout<<'\n';
}


void bktr(int k)
{
    for(int i=1;i<=n;i++)
    {
        sol[k]=i;
    if(valid(k))
        if(k==p)
            tipar(k);
        else
            bktr(k+1);
    }
}

int main()
{
    fin>>n>>p;
    bktr(1);
    return 0;
}

Se citesc două numere naturale nenule n și k. Să se afişeze, în ordine lexicografică, submulțimile de câte k elemente ale mulţimii {1,2,..,n}.

#include <fstream>

using namespace std;
ifstream fin("combinari.in");
ofstream fout("combinari.out");
int n, x[100],p;

void tipar(int k){
    for(int i=1 ; i<=k ; ++i)
        fout << x[i] << " ";
    fout << endl;
}
bool valid(int k){
    for(int i=1;i<k;i++)
        if(x[i]==x[k])
            return false;
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            if(k==p)
                tipar(k);
            else
                back(k+1);
        }
    }

}


int main()
{
    fin>>n>>p;
    back(1);
    return 0;
}

Se citește un număr natural nenul n. Să se afişeze, în ordine lexicografică, toate submulțimile nevide ale mulţimii {1,2,..,n}.

#include <fstream>

using namespace std;
ifstream fin("submultimi.in");
ofstream fout("submultimi.out");
int n, x[100];

void afis(int k){
    for(int i=1 ; i<=k ; ++i)
        fout << x[i] << " ";
    fout << endl;
}
bool valid(int k){
    if(k == 1)
        return true;
    if(x[k] > x[k-1])
        return true;
    return false;
}
void back(int k){
    for(int i=1;i<=n;++i)
    {
        x[k]=i;
        if(valid(k))
        {
            afis(k);
            back(k+1);
        }
    }
}


int main()
{
    fin>>n;
    back(1);
    return 0;
}

Se dă o tablă dreptunghiulară formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona aflată la poziția is, js se află un șoarece care se poate deplasa pe tablă trecând din zona curentă în zona învecinată cu aceasta pe linie sau pe coloană. Scopul sau este să ajungă la o bucată de brânză aflată în zona de la poziția ib, jb, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați câte modalități prin care șoarecele poate ajunge de la poziția inițială la cea a bucății de brânză există.
#include <fstream>

using namespace std;
ifstream fin("soarece.in");
ofstream fout("soarece.out");
int n,m,L[100][100],xs,ys,xb,yb,nrsol;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>L[i][j];
    fin>>xs>>ys>>xb>>yb;
}
void afisare()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if(L[i][j]==2)
                fout<<"* ";
            else
                fout<<L[i][j]<<" ";
        fout<<"\n";
    }
    fout<<'\n';
}
void bktPlan(int x,int y)
{
    int xv,yv;
    for(int i=0;i<4;i++)
    {
        xv=x+dx[i];
        yv=y+dy[i];
        if(xv>0&&xv<=n&&yv>0&&yv<=m&&L[xv][yv]==0)
        {
            L[x][y]=2;
            if(xv==xb&&yv==yb)
            {
                nrsol++;
              //afisare();
            }
            else
                bktPlan(xv,yv);
            L[x][y]=0;
        }
    }
}
int main()
{
    citire();
    bktPlan(xs,ys);
    fout<<nrsol;
    return 0;
}


Se dă o tablă de șah formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. În zona de coordonate 1 1 se află un cal care se poate deplasa pe tablă în L, ca la șah, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care calul poate ajunge în zona de coordonate n m – unde se află o căpiță de fân.

#include <fstream>

using namespace std;
int n,m,L[100][100],xs,ys,xb,yb,nrsol;
int dx[]={-2,-2,-1,1,2,2,1,-1},dy[]={-1,1,2,2,1,-1,-2,-2};

ifstream fin ("traseucal.in");
ofstream fout ("traseucal.out");

void citire()
{
    fin>>n>>m;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            fin>>L[i][j];
            L[i][j]=-L[i][j];
        }
    xs=ys=1;
    xb=n;
    yb=m;
}

void afisare()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            if (L[i][j]==-1)
                fout<<"0 ";
            else
                fout<<L[i][j]<<" ";
        fout<<endl;
    }
}
void bktPlan(int x,int y,int k)
{
    L[x][y]=k;
    if (x==xb && y==yb)
    {
        afisare();
        nrsol++;
    }
    else
        for(int i=0;i<8;i++)
        {
            int xv=x+dx[i];
            int yv=y+dy[i];
            if(xv>0 && xv<=n && yv>0 && yv<=m && L[xv][yv]==0 && nrsol==0)
                bktPlan(xv,yv,k+1);
        }
    L[x][y]=0;
}
int main()
{
    citire();
    bktPlan(xs,ys,1);
    return 0;
}

Se consideră o tablă de joc de formă dreptunghiulară, împărţită în n lini şi m coloane. Se obţin astfel n*m zone şi se cunoaște înălțimea fiecărei zone. La o poziție cunoscută – linia istart, coloana jstart se află o bilă care se poate deplasa pe o poziție vecină (sus, jos, stânga, dreapta) doar dacă înălțimea poziției vecine este strict mai mică decât înălțimea poziției curente.

Determinați numărul maxim de zone prin care poate să treacă bila pentru a ajunge pe una dintre marginile tablei de joc.

#include <fstream>

using namespace std;

ifstream fin("bila.in");
ofstream fout("bila.out");

int xi,xj,n,m;
int a[25][25];
int pasi,maxim;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fin>>a[i][j];
        fin>>xi>>xj;
}
void backPlan(int i,int j,int pasi)
{
    if(i==n || i==1 || j==m || j==1)
    {
        if(pasi>maxim)
            maxim=pasi;
    }
    else
    {
        if(a[i+1][j]<a[i][j])
            backPlan(i+1,j,pasi+1);
        if(a[i-1][j]<a[i][j])
            backPlan(i-1,j,pasi+1);
        if(a[i][j+1]<a[i][j])
            backPlan(i,j+1,pasi+1);
        if(a[i][j-1]<a[i][j])
            backPlan(i,j-1,pasi+1);
    }
}

int main()
{
    citire();
    backPlan(xi,xj,1);
    fout<<maxim;
    return 0;
}

Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu n linii și m coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate (1, 1) și trebuie să ajungă în celula de cordonate (n,m).

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("hercule.in");
ofstream fout("hercule.out");

int n,m, L[15][15],aux[15][15],nrsol;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void citire()
{
    fin>>n>>m;
    for (int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            fin>>L[i][j];
}
void bordare()
{
    for (int i=0; i<=n+1; i++)
        L[i][0]=L[i][m+1]=0;
    for(int j=0;j<=m+1;j++)
        L[0][j]=L[n+1][j]=0;
}
void bktplan(int x,int y,int pas)
{
    if(x==n&&y==m)
        nrsol++;
    else
    {
        aux[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int xv=x+dx[i];
            int yv=y+dy[i];
            if(aux[xv][yv]==0&&L[xv][yv]-pas>=1)
                bktplan(xv,yv,pas+1);
        }
        aux[x][y]=0;
    }
}
int main()
{
    citire();
    bordare();
    bktplan(1,1,1);
    fout<<nrsol;
    return 0;
}

sudoxu

#include <fstream>
using namespace std;
ifstream f("sudoku.in");
ofstream g("sudoku.out");
int a[10][10],i,j,n,k;//k=nivelul curent in stiva, n=inaltimea stivei
//in stiva punem indicii elementele din matrice care sunt zero (necompletate)
int st[3][100],as,ev,gasit;
//as=are succesor, ev=nivelul k e corect completat (valid)
void succesor()
{
    if(a[st[1][k]][st[2][k]]<9)
    {
        a[st[1][k]][st[2][k]]++;
        as=1;
    }
    else as=0;
}
void valid()
{
    int i,j;
    ev=1;
    //parcurg linia
    for(j=1;j<=9;j++)
        if(j!=st[2][k]&&a[st[1][k]][j]==a[st[1][k]][st[2][k]])
          ev=0;
    //parcurg coloana elementului de pe nivelul k
     for(i=1;i<=9;i++)
        if(i!=st[1][k]&&a[i][st[2][k]]==a[st[1][k]][st[2][k]])
          ev=0;
     //parcurg careul
     if(st[1][k]>=1&&st[1][k]<=3&&st[2][k]>=1&&st[2][k]<=3)
          {
             for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;
          }
     else
      if(st[1][k]>=1&&st[1][k]<=3&&st[2][k]>=4&&st[2][k]<=6)
            {for(i=1;i<=3;i++)
                for(j=4;j<=6;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
      else
        if(st[1][k]>=1&&st[1][k]<=3&&st[2][k]>=7&&st[2][k]<=9)
            {for(i=1;i<=3;i++)
                for(j=7;j<=9;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
       else
         if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=1&&st[2][k]<=3)
            {for(i=4;i<=6;i++)
                for(j=1;j<=3;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
      else
        if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=4&&st[2][k]<=6)
            {for(i=4;i<=6;i++)
                for(j=4;j<=6;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
        else
          if(st[1][k]>=4&&st[1][k]<=6&&st[2][k]>=7&&st[2][k]<=9)
            {for(i=4;i<=6;i++)
                for(j=7;j<=9;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
        else
         if(st[1][k]>=7&&st[1][k]<=9&&st[2][k]>=1&&st[2][k]<=3)
            {for(i=7;i<=9;i++)
                for(j=1;j<=3;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
        else
         if(st[1][k]>=7&&st[1][k]<=9&&st[2][k]>=4&&st[2][k]<=6)
            {for(i=7;i<=9;i++)
                for(j=4;j<=6;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
          else
           if(st[1][k]>=7&&st[1][k]<=9&&st[2][k]>=7&&st[2][k]<=9)
            {for(i=7;i<=9;i++)
                for(j=7;j<=9;j++)
                  if(a[st[1][k]][st[2][k]]==a[i][j]&&(i!=st[1][k]||j!=st[2][k]))
                    ev=0;}
}
void tipar()
{
    int i,j;
    for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
            g<<a[i][j]<<" ";
        g<<endl;
    }
    gasit=1;
}
int main()
{
    for(i=1;i<=9;i++)
      for(j=1;j<=9;j++)
      {
          f>>a[i][j];
          if(a[i][j]==0)
          {
              n++;
              st[1][n]=i; //linia
              st[2][n]=j; //coloana
          }
      }
    k=1;
    while(k>0&&!gasit)
    {
        do
        {
            succesor();
            if(as)
                valid();
        }while(as&&!ev);
    if(as)
        if(k==n)
          tipar();
        else
          k++;
    else {a[st[1][k]][st[2][k]]=0;k--;}
    }
    return 0;
}