Backtracking în C++: generarea permutărilor

Backtracking construiește soluții pas cu pas, încearcă alegeri valide și revine atunci când trebuie explorată o altă variantă. O permutare a numerelor 1 până la n conține fiecare număr exact o dată. Exemplul permite să urmărim explicit alegerea, apelul recursiv și anularea alegerii.

Metoda nu este o optimizare magică. Dacă trebuie afișate toate cele n! permutări, numărul rezultatelor crește factorial. Rolul verificărilor este să evite ramuri care nu pot produce soluții valide, nu să elimine costul rezultatului cerut.

Cum funcționează

Vectorul x păstrează soluția parțială. La nivelul k alegem valoarea de pe poziția k. Tabloul used arată ce valori sunt deja folosite, astfel încât verificarea disponibilității să fie constantă. Pentru fiecare candidat v nefolosit, îl scriem, îl marcăm, explorăm nivelul următor și apoi îl demarcăm.

Când k=n, toate pozițiile sunt completate și afișăm soluția. Acesta este cazul terminal, diferit de verificarea unui candidat. Un prefix valid poate să nu fie încă o soluție completă. Amestecarea acestor două întrebări produce afișări premature sau accesarea unei poziții dincolo de vector.

Revenirea nu șterge obligatoriu valoarea numerică din x[k]. Ea restabilește starea care controlează alegerile, aici used[v]. Valoarea din x[k] va fi suprascrisă la următoarea alegere. În alte probleme, poate fi nevoie să refaci o sumă, un marcaj de celulă sau o mulțime de restricții; responsabilitatea trebuie să fie simetrică față de alegere.

Exemplu urmărit pas cu pas

Pentru n=3, prima ramură alege 1, apoi 2, apoi 3 și afișează 1 2 3. La revenire eliberează 3, apoi eliberează 2 și încearcă 3 pe a doua poziție. Ultima valoare disponibilă este acum 2, deci apare 1 3 2.

După epuizarea ramurilor care încep cu 1, se revine la prima poziție și se încearcă 2. Parcurgerea candidaților în ordine crescătoare produce permutările în ordine lexicografică. Programul limitează n la intervalul 1..8, pentru a păstra afișarea rezonabilă în exemple.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int n, x[9];
bool used[9] = {};
void back(int k) {
    if (k == n) {
        for (int i = 0; i < n; ++i)
            std::cout << x[i] << (i + 1 == n ? '\n' : ' ');
        return;
    }
    for (int v = 1; v <= n; ++v)
        if (!used[v]) {
            x[k] = v;
            used[v] = true;
            back(k + 1);
            used[v] = false;
        }
}
int main() {
    std::cin >> n;
    back(0);
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n;
std::vector<int> x(9);
std::vector<char> used(9, 0);
void back(int k) {
    if (k == n) {
        for (int i = 0; i < n; ++i)
            std::cout << x[i] << (i + 1 == n ? '\n' : ' ');
        return;
    }
    for (int v = 1; v <= n; ++v)
        if (!used[v]) {
            x[k] = v;
            used[v] = true;
            back(k + 1);
            used[v] = false;
        }
}
int main() {
    std::cin >> n;
    back(0);
}

De ce funcționează și cât costă

Înainte de nivelul k, primele k poziții conțin valori distincte și used descrie exact acele valori. Fiecare alegere validă păstrează proprietatea. Fiecare permutare are un unic șir de alegeri, deci este produsă o singură dată.

Afișarea tuturor rezultatelor cere O(n*n!) operații doar pentru cele n valori ale fiecărei permutări. Stiva are adâncime O(n), iar vectorii folosesc O(n) memorie. Memoria nu este factorială dacă afișăm soluțiile pe rând.

Greșeli frecvente

Dacă uiți demarcarea după recursie, următoarele ramuri văd valori ocupate incorect. Dacă treci la k+1 înainte de alegere, soluția conține poziții necompletate. Nu confunda permutările cu aranjamentele sau combinările.

Exersează

Scrie permutările pentru n=3 și explică ce s-ar întâmpla dacă used[v] nu ar mai deveni false după apel.

Rezolvare explicată: Sunt șase: 123,132,213,231,312,321. Fără demarcare, valorile primei ramuri rămân ocupate și blochează explorarea corectă a celorlalte soluții.

Continuă să înveți

Recursivitate, vectori și complexitate.

Întrebări frecvente

Ce înseamnă revenirea în backtracking?

După explorarea unei alegeri, refaci starea necesară pentru alternative. În exemplul permutărilor, eliberezi valoarea marcată în used înainte de următorul candidat.

De ce folosim un vector de marcaje?

Permite verificarea rapidă a valorilor deja alese. Fără el, am putea căuta candidatul în prefix, dar fiecare verificare ar costa până la O(n).

Cum obțin ordinea lexicografică?

În acest exemplu, încerci candidații în ordine crescătoare la fiecare poziție. Primul loc diferit dintre două soluții determină ordinea lor.

Backtracking este același lucru cu recursivitatea?

Nu. Recursivitatea este un mecanism de apel. Backtracking este o strategie de explorare cu alegeri și reveniri, care poate avea și implementări iterative.

De ce nu folosim n foarte mare?

Numărul permutărilor este n!, iar simpla lor afișare devine enormă. Restricțiile cerinței trebuie verificate înainte să alegi generarea tuturor soluțiilor.