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)

submulțimi ale unei mulțimi cu n elemente: $2^n$ (cu tot cu ∅);
submulțimi NEVIDE: $2^n - 1$ ;
submulțimi cu EXACT k elemente: $C_n^k$ ;
cuvinte de lungime k din n simboluri (cu repetiție): $n^k$ ;
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 ✓.

Greșeli frecvente

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

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];

void back(int k) {
    if (k > n) {
        cout << "{";
        for (int i = 1; i <= n; i++)
            if (st[i]) cout << i;
        cout << "} ";
        return;
    }
    for (int v = 0; v <= 1; v++) {
        st[k] = v;
        back(k + 1);
    }
}

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

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