Backtracking în C++

Ce este Backtracking?

Backtracking = tehnică de rezolvare a problemelor prin încercare și revenire.

Principiu: construim soluția pas cu pas, și când ajungem într-un punct mort, revenim (back) și încercăm altă variantă.

Structura Generală

Copiază
1void backtrack(int pas) {
2    if (pas == n) {
3        // Afișăm soluția
4        return;
5    }
6    
7    for (fiecare valoare posibilă v) {
8        if (esteValid(v)) {
9            solutie[pas] = v;
10            backtrack(pas + 1);
11            // revenire automată
12        }
13    }
14}

Problema 1: Permutări

Generează toate permutările de n elemente.

Copiază
1#include <iostream>
2using namespace std;
3
4int n, sol[20];
5bool folosit[20];
6
7void afiseaza() {
8    for (int i = 0; i < n; i++)
9        cout << sol[i] << " ";
10    cout << endl;
11}
12
13void permutari(int pas) {
14    if (pas == n) {
15        afiseaza();
16        return;
17    }
18    
19    for (int i = 1; i <= n; i++) {
20        if (!folosit[i]) {
21            sol[pas] = i;
22            folosit[i] = true;
23            permutari(pas + 1);
24            folosit[i] = false;
25        }
26    }
27}
28
29int main() {
30    cin >> n;
31    permutari(0);
32    return 0;
33}

Problema 2: Combinări

Generează toate combinările de n elemente luate câte k.

Copiază
1int n, k, sol[20];
2
3void combinari(int pas, int start) {
4    if (pas == k) {
5        for (int i = 0; i < k; i++)
6            cout << sol[i] << " ";
7        cout << endl;
8        return;
9    }
10    
11    for (int i = start; i <= n; i++) {
12        sol[pas] = i;
13        combinari(pas + 1, i + 1);
14    }
15}
16
17// Apel: combinari(0, 1);

Problema 3: Problema Reginelor

Plasează n regine pe o tablă n×n fără să se atace.

Copiază
1int n, col[20];
2
3bool esteValid(int linie, int coloana) {
4    for (int i = 0; i < linie; i++) {
5        // Verifică coloana
6        if (col[i] == coloana) return false;
7        // Verifică diagonalele
8        if (abs(col[i] - coloana) == abs(i - linie)) return false;
9    }
10    return true;
11}
12
13void regine(int linie) {
14    if (linie == n) {
15        // Afișează soluția
16        for (int i = 0; i < n; i++)
17            cout << col[i] + 1 << " ";
18        cout << endl;
19        return;
20    }
21    
22    for (int j = 0; j < n; j++) {
23        if (esteValid(linie, j)) {
24            col[linie] = j;
25            regine(linie + 1);
26        }
27    }
28}

Când să folosești Backtracking?

• •Generare permutări/combinări/aranjamente
• •Probleme de optimizare cu spațiu mic
• •Căutare în labirint
• •Jocuri (Sudoku, N-regine)
• •Când nu există altă metodă mai eficientă

Exerciții BAC/Olimpiadă

1. •Generează toate submulțimile unei mulțimi
2. •Problema labirintului (găsește drumul)
3. •Partiționarea unui număr în sumă de numere

---

Găsește un profesor de informatică pentru pregătire BAC/Olimpiadă!