Backtracking: ideea

Generează TOATE soluțiile posibile construindu-le element cu element; când o alegere nu mai poate duce la soluție, REVINE (back) și încearcă următoarea variantă.

La BAC (profil matematică-informatică) apare mai ales ca subiect teoretic: "câte soluții generează", "care e a k-a soluție", "ce condiție de continuare lipsește".

Exemplul canonic: permutările

Permutările mulțimii {1, 2, 3} generate în ordine lexicografică:

$123, \; 132, \; 213, \; 231, \; 312, \; 321$

Numărul soluțiilor: $3! = 6$ . Regula de aur: soluțiile apar în ordine LEXICOGRAFICĂ (crescătoare ca "numere").

Întrebare tip BAC. A 4-a permutare generată pentru {1,2,3,4} dacă primele sunt 1234, 1243, 1324? Următoarea: 1342.

Alte generări clasice

submulțimile unei mulțimi cu n elemente: $2^n$ soluții;
produs cartezian / cuvinte de lungime k cu n simboluri: $n^k$ ;
combinări: submulțimi cu exact k elemente, în ordine crescătoare: $C_n^k$ .

Greedy: ideea

La fiecare pas alege varianta LOCAL optimă, fără revenire. Rapid, dar corect doar pentru probleme cu structură specială.

Exemplu clasic: plata unei sume cu bancnote de 50, 10, 5, 1 lei. Pentru suma 87: iei 1×50 (rămân 37), 3×10 (rămân 7), 1×5 (rămân 2), 2×1. Total 7 bancnote, soluția optimă.

Contra-exemplu (de ce greedy poate greși): cu monede de 1, 3, 4 și suma 6, greedy alege 4+1+1 (3 monede), dar optimul e 3+3 (2 monede).

Greșeli frecvente

La "a k-a soluție", generează ordonat pe hârtie, nu ghici.
Numărul submulțimilor include mulțimea vidă: $2^n$ cu tot cu ea.
Greedy nu se "repară" ulterior: dacă problema cere optim garantat și structura nu e potrivită, e nevoie de altă tehnică.

EXEMPLU, ÎN 4 LIMBAJE

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#include <iostream>
using namespace std;

int n = 3, st[10];
bool folosit[10];

void afiseaza() {
    for (int i = 1; i <= n; i++) cout << st[i];
    cout << " ";
}

void back(int k) {
    if (k > n) { afiseaza(); return; }
    for (int v = 1; v <= n; v++)
        if (!folosit[v]) {
            folosit[v] = true;
            st[k] = v;
            back(k + 1);
            folosit[v] = false;
        }
}

int main() {
    back(1);
    return 0;
}

Backtracking și Greedy