# Backtracking și Greedy

> Pagina: https://bacalaurescu.ro/informatica/lectii/backtracking-si-greedy/backtracking-si-greedy-bac
> Markdown: https://bacalaurescu.ro/informatica/lectii/backtracking-si-greedy/backtracking-si-greedy-bac.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Backtracking și Greedy](https://bacalaurescu.ro/informatica/lectii/backtracking-si-greedy)
Actualizat: 2026-11-01

Cele două tehnici la nivel de BAC: recunoaștere, numărare de soluții și alegerea locală optimă.

## Pe scurt pentru BAC

- Backtracking construiește soluțiile element cu element și revine la următoarea variantă când o alegere nu mai poate duce la soluție.
- Permutările mulțimii {1, 2, 3} apar în ordinea 123, 132, 213, 231, 312, 321, adică $3! = 6$ soluții.
- Submulțimile unei mulțimi cu n elemente sunt $2^n$, cuvintele de lungime k din n simboluri sunt $n^k$, iar combinările sunt $C_n^k$.
- Pentru suma 87 cu bancnote de 50, 10, 5 și 1 lei, greedy folosește 7 bancnote, soluția optimă.
- Cu monede de 1, 3, 4 și suma 6, greedy alege 4+1+1, dar optimul este 3+3.

## 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

1. **submulțimile** unei mulțimi cu n elemente: $2^n$ soluții;
2. **produs cartezian / cuvinte** de lungime k cu n simboluri: $n^k$;
3. **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).

> [!RETINE]
> Backtracking = explorare completă cu revenire, soluții în ordine lexicografică, numărul lor dat de formulele de combinatorică. Greedy = alegere locală, fără revenire, fără garanție generală de optim.

## Greșeli frecvente

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