# Generarea submulțimilor și numărarea soluțiilor

> Pagina: https://bacalaurescu.ro/informatica/lectii/backtracking-si-greedy/generarea-submultimilor
> Markdown: https://bacalaurescu.ro/informatica/lectii/backtracking-si-greedy/generarea-submultimilor.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

Vectorul caracteristic, ordinea generării și formulele de numărare cerute la grile.

## Pe scurt pentru BAC

- O submulțime a lui {1..n} se codifică printr-un șir de n biți, unde bitul i spune dacă elementul i apare (1) sau nu (0).
- Submulțimile nevide sunt $2^n - 1$, cele cu exact k elemente sunt $C_n^k$, iar permutările sunt $n!$.
- Submulțimea {1,3} pentru n=3 are biții 101, deci e a 6-a generată, numărând de la mulțimea vidă.
- Submulțimile cu cel puțin 2 elemente ale lui {1,2,3,4} sunt $2^4 - 1 - C_4^1 = 16 - 1 - 4 = 11$.
- Grilele cer de obicei numărul de soluții, a k-a soluție sau vecina ei, toate rezolvabile cu ordinea lexicografică, fără să rulezi programul.

## Vectorul caracteristic

O submulțime a mulțimii {1..n} = un șir de n biți: bitul i spune dacă elementul i APARE (1) sau NU (0).

Pentru n = 3, cele $2^3 = 8$ submulțimi, în ordinea numărării binare:

| biți | submulțimea |
|---|---|
| 000 | ∅ |
| 001 | {3} |
| 010 | {2} |
| 011 | {2,3} |
| 100 | {1} |
| 101 | {1,3} |
| 110 | {1,2} |
| 111 | {1,2,3} |

## Formulele de numărare (setul complet de grile)

1. submulțimi ale unei mulțimi cu n elemente: $2^n$ (cu tot cu ∅);
2. submulțimi NEVIDE: $2^n - 1$;
3. submulțimi cu EXACT k elemente: $C_n^k$;
4. cuvinte de lungime k din n simboluri (cu repetiție): $n^k$;
5. permutări: $n!$; aranjamente: $A_n^k$.

**Exemplu.** Câte submulțimi cu cel puțin 2 elemente are {1,2,3,4}? $2^4 - 1 - C_4^1 = 16 - 1 - 4 = 11$.

## "A câta soluție este...?" (tiparul de subiect)

Generarea pe vector caracteristic urmează NUMĂRAREA BINARĂ: submulțimea {1,3} pentru n=3 are biții 101 = 5 în binar → e a 6-a generată (numărând de la ∅ = prima). Invers: a 7-a soluție are indicele 6 = 110 → {1,2}.

## Backtracking pe subprograme (recunoaștere)

Schema generică: la pasul k alegi o valoare validă, avansezi; când nu mai există valori, REVII la pasul k-1. Grilele cer de obicei doar: numărul de soluții, a k-a soluție, sau soluția anterioară/următoare uneia date: toate rezolvabile cu ordinea lexicografică, fără a "rula" programul.

**Exemplu.** Permutările lui {1,2,3} în ordine: 123, 132, 213, 231, 312, 321. Anterioara lui 312? → 231 ✓.

> [!RETINE]
> Submulțimi = numărare binară pe vector caracteristic; 2^n totale. La "a k-a soluție", scrie k-1 în binar pe n biți. Permutările merg lexicografic, ca în dicționar.

## Greșeli frecvente

1. ∅ se numără printre submulțimi: totalul e 2^n, nu 2^n - 1.
2. Corespondența soluție ↔ index: a k-a soluție are reprezentarea k-1 (numărarea începe de la 0).
3. La permutări, următoarea lexicografică nu e "rotire": compară poziție cu poziție.