Generări combinatoriale

De ce contează?

Vrei să încerci toate combinațiile posibile de topinguri la o pizza: cu sau fără fiecare ingredient. Le construiești sistematic — pentru fiecare ingredient decizi „pun / nu pun" și explorezi toate ramurile. Aceasta e ideea din spatele tuturor generărilor combinatoriale.

Ce sunt generările combinatoriale

Multe probleme cer să generezi toate configurațiile de un anumit tip: submulțimi, permutări, combinări, aranjamente. Toate folosesc același schelet — backtracking: construiești soluția pas cu pas, încerci fiecare opțiune, și revii când o ramură s-a epuizat.

Scheletul backtracking

genereaza(pas):
    daca solutia e completa:
        proceseaza solutia (afiseaza / numara)
        intoarce-te
    pentru fiecare optiune valida la acest pas:
        alege optiunea
        genereaza(pas + 1)        // exploreaza mai departe
        anuleaza alegerea         // BACKTRACK: revii

Observația-cheie

Cele trei mișcări — alege, explorează, anulează — sunt inima backtracking-ului. „Anulează" (backtrack) e ce-l deosebește de o simplă recursie: după ce ai explorat o ramură, revii la starea de dinainte ca să încerci alta.

Exemplu: toate șirurile de `n` biți

Generăm toate combinațiile de 0/1 de lungime n (echivalent cu toate submulțimile):

#include <iostream>
using namespace std;

int sol[20], n;

void genereaza(int pas) {
    if (pas == n) {                 // caz de baza: solutie completa
        for (int i = 0; i < n; i++) cout << sol[i];
        cout << "\n";
        return;
    }
    for (int val = 0; val <= 1; val++) {    // optiunile: 0 sau 1
        sol[pas] = val;             // alege
        genereaza(pas + 1);         // exploreaza
        // anularea e implicita: sol[pas] se rescrie la urmatoarea iteratie
    }
}

int main() {
    n = 3;
    genereaza(0);       // 000, 001, 010, 011, 100, 101, 110, 111
    return 0;
}

Pentru n = 3 produce toate cele 2³ = 8 șiruri.

De ce explodează timpul

Numărul de configurații crește exploziv: submulțimi 2ⁿ, permutări n!, etc. Generarea tuturor e fezabilă doar pentru n mic — tipic n ≤ 20 la submulțimi, n ≤ 10–11 la permutări.

Tip	Câte	n rezonabil
submulțimi	2ⁿ	≤ 20
permutări	n!	≤ 10

Complexitate

Generare	Timp
toate submulțimile	O(2ⁿ · n)
toate permutările	O(n! · n)

Greșeli frecvente

Capcane reale la generările combinatoriale:

Uiți cazul de bază: recursia nu se oprește → buclă infinită sau stack overflow.
Nu anulezi alegerea (backtrack): la structuri care marchează stare (ex. folosit[] la permutări), uiți să o resetezi → soluții greșite sau lipsă.
Generezi pentru n mare: 2ⁿ sau n! explodează; verifică limita lui n din enunț.
Procesezi soluția prea devreme: afișezi înainte ca soluția să fie completă → rezultate parțiale.

De reținut

Backtracking = alege, explorează, anulează — scheletul tuturor generărilor.
Cazul de bază recunoaște soluția completă și o procesează; fără el, recursia nu se oprește.
Numărul de soluții e exponențial/factorial → fezabil doar pentru n mic.