🌳 Backtracking

Backtracking este o tehnică algoritmică de căutare exhaustivă sistematică cu posibilitatea de a reveni (backtrack) atunci când o soluție parțială nu poate fi extinsă la o soluție completă validă.

void backtracking(int nivel) {
    if (solutie_completa(nivel)) {
        afiseazaSolutie();
        return;
    }
    for (fiecare valoare posibila v) {
        if (esteValid(nivel, v)) {
            stiva[nivel] = v;         // alege valoarea
            backtracking(nivel + 1); // explorează mai departe
            stiva[nivel] = 0;         // BACKTRACK — dezalege
        }
    }
}

Generăm toate aranjamentele posibile ale elementelor {1, 2, ..., n}. Numărul de permutări = n!

int n, st[20];
bool folosit[20];

void permutari(int nivel) {
    if (nivel == n + 1) {
        for (int i = 1; i <= n; i++)
            cout << st[i] << " ";
        cout << endl;
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!folosit[v]) {
            st[nivel] = v;
            folosit[v] = true;
            permutari(nivel + 1);
            st[nivel] = 0;         // backtrack
            folosit[v] = false;   // backtrack
        }
    }
}

Generăm toate submulțimile de câte k elemente din {1, 2, ..., n}. Numărul de combinări = C(n,k) = n! / (k! × (n-k)!)

int n, k, st[20];

void combinari(int nivel, int startVal) {
    if (nivel == k + 1) {
        for (int i = 1; i <= k; i++)
            cout << st[i] << " ";
        cout << endl;
        return;
    }
    for (int v = startVal; v <= n; v++) {
        st[nivel] = v;
        combinari(nivel + 1, v + 1);  // elementele cresc strict
        st[nivel] = 0;
    }
}

Generăm toate submulțimile (inclusiv mulțimea vidă) ale unei mulțimi cu n elemente. Numărul total = 2ⁿ.

int n;

void submultimi(int nivel) {
    // Afișăm submulțimea curentă (elementele cu st[i]=1)
    cout << "{";
    bool primul = true;
    for (int i = 1; i <= n; i++)
        if (st[i] == 1) {
            if (!primul) cout << ",";
            cout << i;
            primul = false;
        }
    cout << "} ";

    if (nivel == n + 1) return;

    // Fiecare element poate fi inclus (1) sau exclus (0)
    st[nivel] = 1; submultimi(nivel + 1);
    st[nivel] = 0; submultimi(nivel + 1);
}

int n, col[15];  // col[i] = coloana reginei de pe linia i

bool esteValid(int linie, int coloana) {
    for (int i = 1; i < linie; i++) {
        if (col[i] == coloana) return false;  // aceeași coloană
        if (abs(col[i] - coloana) == abs(i - linie)) return false;  // diagonală
    }
    return true;
}

void regine(int linie) {
    if (linie == n + 1) {
        afiseazaSolutie();
        return;
    }
    for (int c = 1; c <= n; c++) {
        if (esteValid(linie, c)) {
            col[linie] = c;
            regine(linie + 1);
            col[linie] = 0;  // backtrack
        }
    }
}

Vizualizează cum algoritmul backtracking plasează reginele una câte una, detectează conflictele și revine pentru a încerca alte variante.

int lab[10][10], viz[10][10];
int n, m;  // dimensiuni
int dx[] = {-1, 0, 1, 0};  // sus, dreapta, jos, stânga
int dy[] = { 0, 1, 0, -1};

bool labirint(int x, int y, int xf, int yf) {
    if (x == xf && y == yf) return true;  // am ajuns!

    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=0 && nx<n && ny>=0 && ny<m && !viz[nx][ny] && lab[nx][ny]==0) {
            viz[nx][ny] = 1;         // marcăm ca vizitat
            if (labirint(nx, ny, xf, yf)) return true;
            viz[nx][ny] = 0;         // backtrack — ștergem marcajul
        }
    }
    return false;
}

5 probleme clasice, fiecare cu enunț, exemplu și soluție comentată.

3

000
001
010
011
100
101
110
111

int n, x[15];
void bin(int k) {
    if (k > n) {
        for (int i = 1; i <= n; i++) cout << x[i];
        cout << '\n';
        return;
    }
    for (int v = 0; v <= 1; v++) {
        x[k] = v;
        bin(k + 1);
    }
}
// Apel: bin(1); Generează 2^n șiruri.

3 2

1 2
1 3
2 1
2 3
3 1
3 2

int n, k, x[20];
bool folosit[20];
void aranj(int p) {
    if (p > k) {
        for (int i = 1; i <= k; i++) cout << x[i] << ' ';
        cout << '\n';
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!folosit[v]) {
            x[p] = v;
            folosit[v] = true;
            aranj(p + 1);
            folosit[v] = false;   // backtrack!
        }
    }
}

5 10
3 5 2 7 4

3 5 2
3 7
2 4
3 5 2 (în alte ordini omise)

int n, s, a[25];
bool sel[25];
void sub(int i, int sum) {
    if (i > n) {
        if (sum == s) {
            for (int j = 1; j <= n; j++)
                if (sel[j]) cout << a[j] << ' ';
            cout << '\n';
        }
        return;
    }
    // Decizie: includem a[i]
    sel[i] = true;
    sub(i + 1, sum + a[i]);
    sel[i] = false;       // backtrack
    // Decizie: NU includem a[i]
    sub(i + 1, sum);
}
// Apel: sub(1, 0);
// Optimizare (pruning): if (sum > s) return;

3

123, 124, 125, …, 789  (84 numere)

int k, x[10];
void cresc(int p) {
    if (p > k) {
        for (int i = 1; i <= k; i++) cout << x[i];
        cout << '\n';
        return;
    }
    int start = (p == 1) ? 1 : x[p - 1] + 1;
    for (int v = start; v <= 9; v++) {
        x[p] = v;
        cresc(p + 1);
    }
}

123

ABC
AW
LC

string s, sol;
void decod(int i) {
    if (i == (int)s.size()) {
        cout << sol << '\n';
        return;
    }
    // 1) o singură cifră
    if (s[i] != '0') {
        sol += (char)('A' + (s[i] - '0') - 1);
        decod(i + 1);
        sol.pop_back();   // backtrack
    }
    // 2) două cifre (dacă valoarea ≤ 26)
    if (i + 1 < (int)s.size()) {
        int v = (s[i] - '0') * 10 + (s[i+1] - '0');
        if (v >= 10 && v <= 26) {
            sol += (char)('A' + v - 1);
            decod(i + 2);
            sol.pop_back();
        }
    }
}