Backtracking

Ce este backtracking

Backtracking = tehnica de cautare exhaustiva care construieste solutia pas cu pas, revenind (backtracking) atunci cand constata ca nu poate continua.

Idee: la fiecare pas, incearca toate valorile posibile; daca ajunge intr-o situatie fara iesire, se intoarce la pasul anterior si incearca alta valoare.

---

Structura generala

void back(int pas) {
    if (solutieCompleta(pas)) {
        afiseaza();
        return;
    }
    for (fiecare valoare v posibila) {
        if (esteValid(pas, v)) {
            sol[pas] = v;
            back(pas + 1);
        }
    }
}

---

Exemplu: generare permutari de n elemente

int n, sol[20], folosit[20];

void back(int pas) {
    if (pas == n + 1) {
        for (int i = 1; i <= n; i++) cout << sol[i] << " ";
        cout << "\n";
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!folosit[v]) {
            sol[pas] = v;
            folosit[v] = true;
            back(pas + 1);
            folosit[v] = false;  // revenire
        }
    }
}

int main() {
    cin >> n;
    back(1);
}

---

Exemplu: generare combinari C(n, k)

int n, k, sol[20];

void back(int pas, int start) {
    if (pas == k + 1) {
        for (int i = 1; i <= k; i++) cout << sol[i] << " ";
        cout << "\n";
        return;
    }
    for (int v = start; v <= n; v++) {
        sol[pas] = v;
        back(pas + 1, v + 1);
    }
}

---

Exemplu: generare aranjamente A(n, k)

int n, k, sol[20], folosit[20];

void back(int pas) {
    if (pas == k + 1) {
        for (int i = 1; i <= k; i++) cout << sol[i] << " ";
        cout << "\n";
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!folosit[v]) {
            sol[pas] = v;
            folosit[v] = true;
            back(pas + 1);
            folosit[v] = false;
        }
    }
}

---

Exemplu: generare siruri cu cifre 0-9

int k, sol[20];

void back(int pas) {
    if (pas == k + 1) {
        for (int i = 1; i <= k; i++) cout << sol[i];
        cout << "\n";
        return;
    }
    for (int v = 0; v <= 9; v++) {
        sol[pas] = v;
        back(pas + 1);
    }
}

---

Conditii de continuare (taiere)

Backtracking devine eficient prin taierea ramurilor care nu pot duce la solutie:

if (!esteValid(pas, v)) continue;  // nu continua pe aceasta ramura

---

La examen

• Identifica: ce se pune pe fiecare pozitie? Ce valori pot fi alese? Exista restrictii?
• Permutari: n elemente pe n pozitii, fiecare o singura data → vector folosit[]
• Combinari: ordinea nu conteaza → treci valoarea minima (start) ca parametru
• Aranjamente: ordinea conteaza, fara repetitie → ca permutari dar pe k pozitii
• La revenire: reseteaza tot ce ai modificat (folosit[v] = false)