Generarea elementelor combinatoriale

A genera elementele combinatoriale înseamnă a construi, una câte una, toate configurațiile de un anumit fel care se pot forma cu elementele unei mulțimi. Programa de examen cere șase asemenea configurații: permutările, aranjamentele, combinările, submulțimile, partițiile unui număr natural și partițiile unei mulțimi.

Toate șase se generează prin metoda backtracking și, mai mult, folosesc același algoritm. Se schimbă numai câteva subprograme scurte: valorile care se încearcă pe un nivel, condiția în care o valoare se acceptă, momentul în care soluția este completă și felul în care se afișează. Bucla care coboară pe nivelul următor și revine când valorile s-au epuizat rămâne neschimbată.

Fiecare dintre cele șase este tratată mai jos după același plan: descrierea în limbaj natural, exemplificarea etapelor, subprogramele care se schimbă, programul întreg — și în varianta iterativă, și în cea recursivă — complexitatea și o problemă rezolvată, adică exact ce se cere la examen.

Modelul general

Soluția se construiește într-un vector st, numit și stivă. Pozițiile lui sunt nivelurile de decizie: st[k] este valoarea aleasă pe nivelul k, iar variabila k arată nivelul curent.

Algoritmul folosește cinci subprograme:

• init() pregătește nivelul k, punând în st[k] o valoare aflată chiar înaintea primei valori posibile;
• succesor() trece la valoarea următoare de pe nivelul k și întoarce 0 când valorile s-au epuizat;
• valid() spune dacă valoarea așezată pe nivelul k respectă restricțiile problemei;
• solutie() spune dacă soluția parțială este completă;
• tipar() prelucrează sau afișează soluția completă.

Peste ele stă bucla care nu se schimbă de la o configurație la alta:

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;
    init();

    while (k > 0) {
        as = 1;
        ev = 0;

        // cat timp exista un succesor si acesta nu este valid
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();
            else {
                k++;
                init();
            }
        else
            k--;
    }
}

# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1
init(k)

while k > 0:
    exista = True
    este_valid = False

    # cat timp exista un succesor si acesta nu este valid
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()
        else:
            k += 1
            init(k)
    else:
        k -= 1

Bucla interioară caută pe nivelul curent prima valoare validă. Bucla exterioară stabilește ce urmează: dacă valoarea s-a găsit și soluția este completă, soluția se afișează și căutarea continuă de pe același nivel; dacă soluția nu este completă, se coboară pe nivelul următor; dacă valoarea nu s-a găsit, se revine pe nivelul anterior. Algoritmul se oprește când revenirea de pe nivelul 1 duce la nivelul 0.

De felul în care se apelează init() depinde corectitudinea:

• init() se apelează la fiecare coborâre, nu o singură dată la începutul programului: un nivel la care se ajunge a doua oară trebuie să-și reia valorile de la capăt;
• la revenire nu se apelează init(): nivelul pe care se revine trebuie să continue de la valoarea la care rămăsese, altfel aceleași soluții s-ar genera la nesfârșit.

Ce se schimbă de la o configurație la alta

Se vede aici o deosebire de fond: la unele configurații restricția se verifică în valid(), la altele este impusă chiar prin domeniul valorilor încercate. A doua cale este de preferat, fiindcă nu se mai generează valori care oricum ar fi respinse.

Varianta recursivă

Aceeași căutare se poate scrie și recursiv. Nivelul curent este parametrul subprogramului, coborârea pe nivelul următor se scrie ca apelul bt_recursiv(k + 1), iar pentru revenire nu se scrie nicio instrucțiune: ea se produce la încheierea apelului, când execuția se întoarce în bucla nivelului anterior și continuă cu valoarea următoare.

void bt_recursiv(int k) {
    init(k);
    while (succesor(k))
        if (valid(k)) {
            if (solutie(k))
                tipar();
            else
                bt_recursiv(k + 1);
        }
}

def bt_recursiv(k):
    init(k)
    while succesor(k):
        if valid(k):
            if solutie(k):
                tipar()
            else:
                bt_recursiv(k + 1)

Varianta recursivă este mai scurtă, dar folosește stiva sistemului pentru nivelurile în lucru. Varianta iterativă ține totul în vectorul st și în variabila k. La examen este bună oricare, cu condiția să fie scrisă întreagă.

La fiecare dintre cele șase configurații, programul întreg este dat în amândouă variantele. În C++ varianta recursivă primește nivelul ca parametru, deci îl primesc și subprogramele, iar k, as și ev nu mai sunt necesare; în Python subprogramele rămân neschimbate, fiindcă luau deja nivelul ca parametru.

Permutări

Definiția matematică

Fie A o mulțime finită cu n elemente. O permutare a mulțimii A este o funcție bijectivă f : A → A. Pentru A = {1, 2, …, n}, permutarea se scrie ca șirul valorilor ei, (f(1), f(2), …, f(n)), adică o înșiruire în care fiecare element al mulțimii apare exact o dată.

Numărul permutărilor unei mulțimi cu n elemente este

P(n) = n! = 1 · 2 · 3 · … · n

Formula se obține din regula produsului: pe prima poziție poate fi așezat oricare dintre cele n elemente, pe a doua oricare dintre cele n − 1 rămase, pe a treia oricare dintre cele n − 2 rămase și așa mai departe, iar pe ultima poziție rămâne un singur element. Înmulțind numărul alegerilor de pe fiecare poziție se obține n · (n − 1) · … · 2 · 1.

Prin convenție 0! = 1, deci mulțimea vidă are o singură permutare.

Pentru n = 3, mulțimea {1, 2, 3} are 3! = 6 permutări:

1 2 3    1 3 2    2 1 3    2 3 1    3 1 2    3 2 1

Cum se construiește soluția

Nivelul k este poziția a k-a din șir, iar st[k] este valoarea așezată pe ea. Pe fiecare nivel se încearcă, pe rând, valorile 1, 2, …, n.

O valoare se acceptă dacă nu a mai fost folosită pe nivelurile dinainte, adică dacă st[i] ≠ st[k] pentru orice i < k. Soluția este completă când s-a completat nivelul n.

Extinderea unei soluții parțiale se face coborând pe nivelul următor, unde valorile se iau iar de la 1. Trecerea de la o soluție la următoarea se face rămânând pe nivelul n și încercând valoarea imediat următoare; când pe nivelul n valorile s-au epuizat, se revine pe nivelul n−1.

Exemplificarea etapelor

Pentru n = 3, primele încercări sunt:

Se vede la pasul 6 că soluția se afișează fără să se coboare mai departe, iar la pasul 7 că nivelul 3 se golește înainte de revenire. Continuând, se obțin toate cele 3! = 6 permutări, în ordine: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1.

Programul întreg

Aceleași cinci subprograme, chemate o dată dintr-o buclă și o dată prin apeluri.

#include <iostream>
using namespace std;

int st[20];
int n, k, as, ev;

void init() {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor() {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

int valid() {
    // valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;
    return 1;
}

int solutie() {
    return k == n;                      // sirul e intreg cand are toate cele n pozitii
}

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

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n;
    bt_iterativ();
    return 0;
}

#include <iostream>
using namespace std;

int st[20];
int n;

void init(int k) {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor(int k) {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

int valid(int k) {
    // valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;
    return 1;
}

int solutie(int k) {
    return k == n;                      // sirul e intreg cand are toate cele n pozitii
}

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

void bt_recursiv(int k) {
    init(k);                            // nivelul k isi ia valorile de la capat

    while (succesor(k))                 // cat timp mai e o valoare de incercat
        if (valid(k)) {
            if (solutie(k))
                tipar();              // configuratie intreaga
            else
                bt_recursiv(k + 1);     // se coboara pe nivelul urmator
        }
    /* La incheierea apelului controlul revine pe nivelul k-1, care continua
       cu valoarea urmatoare. Revenirea nu are instructiune scrisa. */
}

int main() {
    cin >> n;
    bt_recursiv(1);
    return 0;
}

n = int(input())
st = [0] * (n + 2)


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


def valid(k):
    # valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for i in range(1, k):
        if st[i] == st[k]:
            return False
    return True


def solutie(k):
    return k == n                       # sirul e intreg cand are toate cele n pozitii


def tipar():
    print(*st[1:n + 1])


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

n = int(input())
st = [0] * (n + 2)


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


def valid(k):
    # valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for i in range(1, k):
        if st[i] == st[k]:
            return False
    return True


def solutie(k):
    return k == n                       # sirul e intreg cand are toate cele n pozitii


def tipar():
    print(*st[1:n + 1])


def bt_recursiv(k):
    init(k)                             # nivelul k isi ia valorile de la capat

    while succesor(k):                  # cat timp mai e o valoare de incercat
        if valid(k):
            if solutie(k):
                tipar()               # configuratie intreaga
            else:
                bt_recursiv(k + 1)      # se coboara pe nivelul urmator
    # La incheierea apelului controlul revine pe nivelul k-1, care continua
    # cu valoarea urmatoare. Revenirea nu are instructiune scrisa.


bt_recursiv(1)

Complexitatea

Se generează n! permutări. Pentru fiecare, afișarea cere n operații, iar verificarea de pe un nivel cere cel mult n−1 comparații. Timpul de executare este deci de ordinul n·n!. Încercările respinse nu schimbă ordinul: numărul nodurilor din arborele de căutare rămâne comparabil cu numărul soluțiilor.

Creșterea este mai rapidă decât la orice funcție exponențială: pentru n = 10 se generează 3 628 800 de permutări, iar pentru n = 12 se trece de 479 de milioane. Generarea tuturor permutărilor se folosește deci numai pentru valori mici ale lui n. Memoria cerută este O(n), fără a socoti soluțiile afișate.

Un exemplu de utilizare

Enunț. La un joc, n copii (2 ≤ n ≤ 9) numerotați de la 1 la n stau pe n locuri numerotate la fel, fiecare copil pe locul cu numărul lui. Ei se așază din nou, astfel încât niciun copil să nu rămână pe locul pe care a stat. Se cere afișarea tuturor așezărilor posibile și a numărului lor.

Exemplu: pentru n = 4 se afișează 9 așezări, printre care 2 1 4 3 și 3 4 1 2, unde valoarea de pe poziția i este numărul copilului care stă pe locul i.

Descrierea soluției în limbaj natural. O așezare este o permutare a celor n copii, deci se generează toate permutările. Condiția „niciun copil nu rămâne pe locul lui” înseamnă că pe nivelul k nu poate sta valoarea k.

Condiția se verifică în valid(), împreună cu cea a permutărilor, nu la soluția completă. Astfel drumurile care ar duce la un copil rămas pe locul lui se abandonează de la primul nivel unde se vede greșeala, în loc să fie completate până la capăt și abia apoi respinse.

Implementarea.

#include <iostream>
using namespace std;

int st[11];
int n, k, as, ev, nr;

void init() {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor() {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

/* Pe langa conditia permutarilor - valori distincte - se cere ca niciun
   copil sa nu ramana pe locul lui, adica st[k] sa fie diferit de k. */
int valid() {
    if (st[k] == k)
        return 0;

    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;

    return 1;
}

int solutie() {
    return k == n;
}

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

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n;
    bt_iterativ();
    cout << "Numarul asezarilor: " << nr << endl;
    return 0;
}

n = int(input())
st = [0] * (n + 1)
nr = 0


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


# Pe langa conditia permutarilor - valori distincte - se cere ca niciun
# copil sa nu ramana pe locul lui, adica st[k] sa fie diferit de k.
def valid(k):
    if st[k] == k:
        return False

    for i in range(1, k):
        if st[i] == st[k]:
            return False

    return True


def solutie(k):
    return k == n


def tipar():
    global nr
    print(*st[1:n + 1])
    nr += 1


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

print("Numarul asezarilor:", nr)

Pentru n = 4 programul afișează 9 așezări, iar pentru n = 5 afișează 44.

Aranjamente

Definiția matematică

Fie A o mulțime cu n elemente și m un număr natural, 0 ≤ m ≤ n. Un aranjament de n elemente luate câte m este o submulțime ordonată cu m elemente a lui A, adică un șir de m elemente distincte alese din A. Două aranjamente se deosebesc fie prin elementele alese, fie prin ordinea lor.

Numărul aranjamentelor de n elemente luate câte m este

A(n,m) = n · (n − 1) · … · (n − m + 1) = n! / (n − m)!

Formula se obține tot din regula produsului: pe prima poziție se poate alege oricare dintre cele n elemente, pe a doua oricare dintre cele n − 1 rămase, iar pe poziția a m-a oricare dintre cele n − m + 1 rămase. Produsul are m factori, nu n.

Pentru m = n se obțin chiar permutările: A(n,n) = n! / 0! = n!. Pentru m = 1, A(n,1) = n.

Pentru n = 4 și m = 2, cele A(4,2) = 4 · 3 = 12 aranjamente ale mulțimii {1, 2, 3, 4} sunt:

1 2   1 3   1 4   2 1   2 3   2 4
3 1   3 2   3 4   4 1   4 2   4 3

Cum se construiește soluția

Reprezentarea și valorile încercate sunt aceleași ca la permutări: nivelul k este poziția a k-a din șir, iar pe el se încearcă valorile 1, 2, …, n, dintre care se acceptă cele nefolosite.

Se schimbă numai lungimea soluției. Soluția este completă la nivelul m, nu la nivelul n, și tot primele m poziții se afișează. Pentru m = n se obțin chiar permutările.

Exemplificarea etapelor

Pentru n = 4 și m = 2:

Se obțin cele 12 aranjamente: 1 2, 1 3, 1 4, 2 1, 2 3, 2 4, 3 1, 3 2, 3 4, 4 1, 4 2, 4 3. Se vede că 1 2 și 2 1 sunt amândouă în listă: la aranjamente ordinea contează.

Subprogramele care se schimbă

Față de permutări se schimbă numai solutie() și tipar().

int st[20];
int n, m, k, as, ev;

int solutie() {
    return k == m;                      // sirul are m pozitii, nu n
}

void tipar() {
    for (int i = 1; i <= m; i++)        // se scriu numai primele m pozitii
        cout << st[i] << " ";
    cout << endl;
}

def solutie(k):
    return k == m                       # sirul are m pozitii, nu n


def tipar():
    print(*st[1:m + 1])                 # se scriu numai primele m pozitii

Programul întreg

Programul de la permutări, cu solutie() și tipar() schimbate.

#include <iostream>
using namespace std;

int st[20];
int n, m, k, as, ev;

void init() {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor() {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

int valid() {
    // valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;
    return 1;
}

int solutie() {
    return k == m;                      // sirul are m pozitii, nu n
}

void tipar() {
    for (int i = 1; i <= m; i++)        // se scriu numai primele m pozitii
        cout << st[i] << " ";
    cout << endl;
}

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n >> m;
    bt_iterativ();
    return 0;
}

#include <iostream>
using namespace std;

int st[20];
int n, m;

void init(int k) {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor(int k) {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

int valid(int k) {
    // valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;
    return 1;
}

int solutie(int k) {
    return k == m;                      // sirul are m pozitii, nu n
}

void tipar() {
    for (int i = 1; i <= m; i++)        // se scriu numai primele m pozitii
        cout << st[i] << " ";
    cout << endl;
}

void bt_recursiv(int k) {
    init(k);                            // nivelul k isi ia valorile de la capat

    while (succesor(k))                 // cat timp mai e o valoare de incercat
        if (valid(k)) {
            if (solutie(k))
                tipar();              // configuratie intreaga
            else
                bt_recursiv(k + 1);     // se coboara pe nivelul urmator
        }
    /* La incheierea apelului controlul revine pe nivelul k-1, care continua
       cu valoarea urmatoare. Revenirea nu are instructiune scrisa. */
}

int main() {
    cin >> n >> m;
    bt_recursiv(1);
    return 0;
}

n, m = map(int, input().split())
st = [0] * (n + 2)


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


def valid(k):
    # valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for i in range(1, k):
        if st[i] == st[k]:
            return False
    return True


def solutie(k):
    return k == m                       # sirul are m pozitii, nu n


def tipar():
    print(*st[1:m + 1])                 # se scriu numai primele m pozitii


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

n, m = map(int, input().split())
st = [0] * (n + 2)


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


def valid(k):
    # valoarea de pe nivelul k nu are voie sa apara pe nivelurile dinainte
    for i in range(1, k):
        if st[i] == st[k]:
            return False
    return True


def solutie(k):
    return k == m                       # sirul are m pozitii, nu n


def tipar():
    print(*st[1:m + 1])                 # se scriu numai primele m pozitii


def bt_recursiv(k):
    init(k)                             # nivelul k isi ia valorile de la capat

    while succesor(k):                  # cat timp mai e o valoare de incercat
        if valid(k):
            if solutie(k):
                tipar()               # configuratie intreaga
            else:
                bt_recursiv(k + 1)      # se coboara pe nivelul urmator
    # La incheierea apelului controlul revine pe nivelul k-1, care continua
    # cu valoarea urmatoare. Revenirea nu are instructiune scrisa.


bt_recursiv(1)

Complexitatea

Se generează A(n,m) aranjamente, fiecare afișat în m pași, iar validarea cere cel mult m−1 comparații. Timpul este de ordinul m·A(n,m).

Numărul crește repede în raport cu amândoi parametrii: A(10,5) = 30 240, iar A(15,7) = 32 432 400. Pentru m = n se ajunge la n!.

Un exemplu de utilizare

Enunț. Se cunosc n orașe (2 ≤ n ≤ 9) și distanțele dintre oricare două dintre ele, date printr-o matrice pătratică. Un curier trebuie să treacă prin exact m orașe distincte, într-o ordine oarecare (2 ≤ m ≤ n). Se cere traseul de lungime minimă și lungimea lui.

Exemplu: pentru n = 4, m = 3 și matricea liniilor 0 5 9 4, 5 0 3 8, 9 3 0 2, 4 8 2 0 se afișează lungimea 5 și traseul 2 3 4.

Descrierea soluției în limbaj natural. Un traseu este un șir de m orașe distincte în care ordinea contează, deci este un aranjament de n luate câte m. Se generează toate aranjamentele.

De fiecare dată când se completează nivelul m, adică traseul este întreg, se adună distanțele dintre orașele vecine din vectorul soluție: de la st[1] la st[2], de la st[2] la st[3] și așa mai departe. Dacă lungimea obținută este mai mică decât cea mai mică lungime găsită până atunci, traseul se păstrează.

Lungimea nu se poate compara mai devreme de nivelul m, fiindcă un traseu cu primele distanțe mari poate fi întregit cu distanțe mici. Se poate însă abandona un drum a cărui lungime parțială a depășit deja minimul găsit — distanțele fiind pozitive, ea nu mai poate scădea.

Implementarea.

#include <iostream>
using namespace std;

int d[11][11];
int st[11], best[11];
int n, m, k, as, ev;
int costMinim = -1;

void init() {
    st[k] = 0;                          // inaintea primei valori, ca succesor() sa dea 1
}

int succesor() {
    if (st[k] < n) {                    // pe nivelul k se incearca valorile 1, 2, ..., n
        st[k]++;
        return 1;
    }
    return 0;                           // valorile s-au terminat: urmeaza revenirea
}

int valid() {
    for (int i = 1; i < k; i++)
        if (st[i] == st[k])
            return 0;
    return 1;
}

int solutie() {
    return k == m;
}

/* Traseul e intreg: i se calculeaza lungimea si se pastreaza daca e cel
   mai scurt de pana acum. */
void tipar() {
    int cost = 0;
    for (int i = 1; i < m; i++)
        cost = cost + d[st[i]][st[i + 1]];

    if (costMinim == -1 || cost < costMinim) {
        costMinim = cost;
        for (int i = 1; i <= m; i++)
            best[i] = st[i];
    }
}

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> d[i][j];

    bt_iterativ();

    cout << costMinim << endl;
    for (int i = 1; i <= m; i++)
        cout << best[i] << " ";
    cout << endl;

    return 0;
}

n, m = [int(x) for x in input().split()]
d = [[0] * (n + 1)]
for i in range(n):
    d.append([0] + [int(x) for x in input().split()])

st = [0] * (n + 1)
best = [0] * (n + 1)
cost_minim = -1


def init(k):
    st[k] = 0                           # inaintea primei valori, ca succesor() sa dea 1


def succesor(k):
    if st[k] < n:                       # pe nivelul k se incearca valorile 1, 2, ..., n
        st[k] += 1
        return True
    return False                        # valorile s-au terminat: urmeaza revenirea


def valid(k):
    for i in range(1, k):
        if st[i] == st[k]:
            return False
    return True


def solutie(k):
    return k == m


# Traseul e intreg: i se calculeaza lungimea si se pastreaza daca e cel
# mai scurt de pana acum.
def tipar():
    global cost_minim
    cost = 0
    for i in range(1, m):
        cost = cost + d[st[i]][st[i + 1]]

    if cost_minim == -1 or cost < cost_minim:
        cost_minim = cost
        best[1:m + 1] = st[1:m + 1]


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

print(cost_minim)
print(*best[1:m + 1])

Combinări

Definiția matematică

Fie A o mulțime cu n elemente și m un număr natural, 0 ≤ m ≤ n. O combinare de n elemente luate câte m este o submulțime cu m elemente a lui A. Ordinea nu are nicio însemnătate: {1, 2, 3} și {3, 1, 2} sunt aceeași submulțime, deci aceeași combinare.

Numărul combinărilor de n elemente luate câte m este

C(n,m) = n! / (m! · (n − m)!) = A(n,m) / m!

A doua scriere arată și de unde vine formula: din fiecare submulțime cu m elemente se obțin, ordonând în toate felurile elementele ei, m! aranjamente deosebite, iar orice aranjament se obține dintr-o singură submulțime. Numărul aranjamentelor este deci de m! ori mai mare decât numărul combinărilor.

Proprietățile folosite cel mai des:

• C(n,m) = C(n, n−m), fiindcă a alege cele m elemente care intră în submulțime este totuna cu a alege cele n − m care rămân afară;
• C(n,0) = C(n,n) = 1;
• C(n,m) = C(n−1, m−1) + C(n−1, m), după cum un element fixat intră sau nu în submulțime; este formula care dă triunghiul lui Pascal;
• C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ, adică numărul tuturor submulțimilor unei mulțimi cu n elemente.

Pentru n = 5 și m = 3, cele C(5,3) = 10 combinări sunt:

1 2 3   1 2 4   1 2 5   1 3 4   1 3 5
1 4 5   2 3 4   2 3 5   2 4 5   3 4 5

Cum se construiește soluția

Fiindcă ordinea nu contează, din toate așezările unei submulțimi trebuie generată una singură. Se alege cea crescătoare: valoarea de pe nivelul k trebuie să fie mai mare decât cea de pe nivelul k−1.

Condiția nu se verifică în valid(), ci se impune prin valorile care se încearcă. Nivelul k pornește de la st[k−1], iar primul apel al lui succesor() îl duce la st[k−1] + 1. Pe primul nivel valorile pornesc de la 1, deci st[0] este 0.

Valorile de pe nivelul k se opresc la n − m + k. Peste această limită nu ar mai rămâne destule valori pentru nivelurile care urmează: pe nivelul k trebuie să mai încapă m − k elemente după valoarea aleasă. Limita nu schimbă rezultatul, dar oprește drumurile care oricum nu se pot întregi.

Exemplificarea etapelor

Pentru n = 5 și m = 3, limita de pe nivelul k este n − m + k, adică 3 pe nivelul 1, 4 pe nivelul 2 și 5 pe nivelul 3.

Se obțin cele C(5,3) = 10 combinări: 1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5, 2 3 4, 2 3 5, 2 4 5, 3 4 5.

Rolul limitei se vede la pasul 7: pe nivelul 2 s-ar putea încerca și valoarea 5, dar 5 depășește n − m + 2 = 4, fiindcă după ea nu ar mai rămâne nicio valoare pentru nivelul 3.

Subprogramele care se schimbă

Față de permutări se schimbă init(), succesor(), valid(), solutie() și tipar(), adică tot ce ține de configurație. Bucla rămâne aceeași.

int st[20];
int n, m, k, as, ev;

void init() {
    if (k == 1)
        st[k] = 0;                      // pe primul nivel valorile pornesc de la 1
    else
        st[k] = st[k - 1];              // pe celelalte, de la valoarea de sub ele plus unu
}

int succesor() {
    // n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    // ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if (st[k] < n - m + k) {
        st[k]++;
        return 1;
    }
    return 0;
}

/* Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
   nimic de verificat aici. */
int valid() {
    return 1;
}

int solutie() {
    return k == m;                      // s-au ales m elemente
}

void tipar() {
    for (int i = 1; i <= m; i++)
        cout << st[i] << " ";
    cout << endl;
}

def init(k):
    if k == 1:
        st[k] = 0                       # pe primul nivel valorile pornesc de la 1
    else:
        st[k] = st[k - 1]               # pe celelalte, de la valoarea de sub ele plus unu


def succesor(k):
    # n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    # ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if st[k] < n - m + k:
        st[k] += 1
        return True
    return False


# Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
# nimic de verificat aici.
def valid(k):
    return True


def solutie(k):
    return k == m                       # s-au ales m elemente


def tipar():
    print(*st[1:m + 1])

Programul întreg

Programul întreg, cu cele cinci subprograme de mai sus.

#include <iostream>
using namespace std;

int st[20];
int n, m, k, as, ev;

void init() {
    if (k == 1)
        st[k] = 0;                      // pe primul nivel valorile pornesc de la 1
    else
        st[k] = st[k - 1];              // pe celelalte, de la valoarea de sub ele plus unu
}

int succesor() {
    // n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    // ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if (st[k] < n - m + k) {
        st[k]++;
        return 1;
    }
    return 0;
}

/* Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
   nimic de verificat aici. */
int valid() {
    return 1;
}

int solutie() {
    return k == m;                      // s-au ales m elemente
}

void tipar() {
    for (int i = 1; i <= m; i++)
        cout << st[i] << " ";
    cout << endl;
}

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n >> m;
    bt_iterativ();
    return 0;
}

#include <iostream>
using namespace std;

int st[20];
int n, m;

void init(int k) {
    if (k == 1)
        st[k] = 0;                      // pe primul nivel valorile pornesc de la 1
    else
        st[k] = st[k - 1];              // pe celelalte, de la valoarea de sub ele plus unu
}

int succesor(int k) {
    // n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    // ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if (st[k] < n - m + k) {
        st[k]++;
        return 1;
    }
    return 0;
}

/* Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
   nimic de verificat aici. */
int valid(int k) {
    return 1;
}

int solutie(int k) {
    return k == m;                      // s-au ales m elemente
}

void tipar() {
    for (int i = 1; i <= m; i++)
        cout << st[i] << " ";
    cout << endl;
}

void bt_recursiv(int k) {
    init(k);                            // nivelul k isi ia valorile de la capat

    while (succesor(k))                 // cat timp mai e o valoare de incercat
        if (valid(k)) {
            if (solutie(k))
                tipar();              // configuratie intreaga
            else
                bt_recursiv(k + 1);     // se coboara pe nivelul urmator
        }
    /* La incheierea apelului controlul revine pe nivelul k-1, care continua
       cu valoarea urmatoare. Revenirea nu are instructiune scrisa. */
}

int main() {
    cin >> n >> m;
    bt_recursiv(1);
    return 0;
}

n, m = map(int, input().split())
st = [0] * (n + 2)


def init(k):
    if k == 1:
        st[k] = 0                       # pe primul nivel valorile pornesc de la 1
    else:
        st[k] = st[k - 1]               # pe celelalte, de la valoarea de sub ele plus unu


def succesor(k):
    # n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    # ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if st[k] < n - m + k:
        st[k] += 1
        return True
    return False


# Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
# nimic de verificat aici.
def valid(k):
    return True


def solutie(k):
    return k == m                       # s-au ales m elemente


def tipar():
    print(*st[1:m + 1])


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

n, m = map(int, input().split())
st = [0] * (n + 2)


def init(k):
    if k == 1:
        st[k] = 0                       # pe primul nivel valorile pornesc de la 1
    else:
        st[k] = st[k - 1]               # pe celelalte, de la valoarea de sub ele plus unu


def succesor(k):
    # n - m + k este ultima valoare care se poate incerca pe nivelul k: peste
    # ea n-ar mai ramane destule valori pentru nivelurile care urmeaza
    if st[k] < n - m + k:
        st[k] += 1
        return True
    return False


# Ordinea crescatoare e impusa prin valorile incercate, deci nu mai e
# nimic de verificat aici.
def valid(k):
    return True


def solutie(k):
    return k == m                       # s-au ales m elemente


def tipar():
    print(*st[1:m + 1])


def bt_recursiv(k):
    init(k)                             # nivelul k isi ia valorile de la capat

    while succesor(k):                  # cat timp mai e o valoare de incercat
        if valid(k):
            if solutie(k):
                tipar()               # configuratie intreaga
            else:
                bt_recursiv(k + 1)      # se coboara pe nivelul urmator
    # La incheierea apelului controlul revine pe nivelul k-1, care continua
    # cu valoarea urmatoare. Revenirea nu are instructiune scrisa.


bt_recursiv(1)

Complexitatea

Se generează C(n,m) combinări, fiecare afișată în m pași, deci timpul este de ordinul m·C(n,m). Încercările care nu duc la o soluție rămân de același ordin, fiindcă limita n − m + k taie tocmai drumurile care nu se pot întregi.

Complexitatea nu este polinomială: pentru m apropiat de n/2, C(n,m) crește exponențial în raport cu n. Pentru n = 20 și m = 10 se generează 184 756 de combinări, iar pentru n = 30 și m = 15 numărul lor trece de 155 de milioane. Acolo unde se cere o singură combinare, de obicei cea optimă, se caută metode care nu le enumeră pe toate.

Un exemplu de utilizare

Enunț. Într-un magazin sunt n produse (2 ≤ n ≤ 20), numerotate de la 1 la n, fiecare cu un preț număr natural. Un client cumpără exact m produse, având la dispoziție suma B. Se cer toate alegerile posibile al căror preț total nu depășește B, precum și cea mai scumpă dintre ele.

Exemplu: pentru n = 5, m = 2, B = 30 și prețurile 12, 7, 25, 9, 18 se afișează alegerile 1 2, 1 4, 1 5, 2 4, 2 5, 4 5, iar cea mai scumpă dintre ele este 1 5, de 30 de lei.

Descrierea soluției în limbaj natural. O alegere de m produse din n este o submulțime cu m elemente, deci o combinare: ordinea în care sunt luate produsele nu schimbă cumpărătura. Se generează toate combinările numerelor de ordine.

De fiecare dată când se completează nivelul m, se adună prețurile celor m produse din vectorul soluție. Dacă suma nu depășește B, alegerea se afișează, iar dacă este mai mare decât cea mai scumpă de până atunci, se păstrează.

Suma nu se poate compara cu B înainte de nivelul m: prețurile fiind pozitive, o sumă parțială mică nu arată cât va fi suma întreagă. Se poate însă abandona un drum în care suma parțială a depășit deja B.

Implementarea.

#include <iostream>
using namespace std;

int pret[21], st[21], best[21];
int n, m, B, k, as, ev;
int celMaiMare = -1;

void init() {
    if (k == 1)
        st[k] = 0;                      // pe primul nivel valorile pornesc de la 1
    else
        st[k] = st[k - 1];              // pe celelalte, de la valoarea de sub ele plus unu
}

int succesor() {
    // n - m + k este ultima valoare care se poate incerca pe nivelul k
    if (st[k] < n - m + k) {
        st[k]++;
        return 1;
    }
    return 0;
}

int valid() {
    return 1;
}

int solutie() {
    return k == m;
}

void tipar() {
    int suma = 0;
    for (int i = 1; i <= m; i++)
        suma = suma + pret[st[i]];

    if (suma <= B) {
        for (int i = 1; i <= m; i++)
            cout << st[i] << " ";
        cout << "- " << suma << " lei" << endl;

        if (suma > celMaiMare) {
            celMaiMare = suma;
            for (int i = 1; i <= m; i++)
                best[i] = st[i];
        }
    }
}

/* as - exista succesor pe nivelul curent
   ev - valoarea asezata pe nivelul curent este valida */
void bt_iterativ() {
    k = 1;                              // se incepe cu primul nivel
    init();

    while (k > 0) {                     // cat timp nu s-a revenit sub nivelul 1
        as = 1;
        ev = 0;

        // se cauta pe nivelul curent prima valoare care se accepta
        while (as && !ev) {
            as = succesor();
            if (as)
                ev = valid();
        }

        if (as)
            if (solutie())
                tipar();              // configuratie intreaga
            else {
                k++;                    // se coboara pe nivelul urmator,
                init();                 // care isi ia valorile de la capat
            }
        else
            k--;                        // valorile s-au terminat: revenire
    }
}

int main() {
    cin >> n >> m >> B;
    for (int i = 1; i <= n; i++)
        cin >> pret[i];

    bt_iterativ();

    if (celMaiMare == -1)
        cout << "nu exista" << endl;
    else {
        cout << "Cea mai scumpa alegere: ";
        for (int i = 1; i <= m; i++)
            cout << best[i] << " ";
        cout << "- " << celMaiMare << " lei" << endl;
    }

    return 0;
}

n, m, B = [int(x) for x in input().split()]
pret = [0] + [int(x) for x in input().split()]
st = [0] * (n + 1)
best = [0] * (n + 1)
cel_mai_mare = -1


def init(k):
    if k == 1:
        st[k] = 0                       # pe primul nivel valorile pornesc de la 1
    else:
        st[k] = st[k - 1]               # pe celelalte, de la valoarea de sub ele plus unu


def succesor(k):
    # n - m + k este ultima valoare care se poate incerca pe nivelul k
    if st[k] < n - m + k:
        st[k] += 1
        return True
    return False


def valid(k):
    return True


def solutie(k):
    return k == m


def tipar():
    global cel_mai_mare
    suma = sum(pret[st[i]] for i in range(1, m + 1))

    if suma <= B:
        print(*st[1:m + 1], "-", suma, "lei")

        if suma > cel_mai_mare:
            cel_mai_mare = suma
            best[1:m + 1] = st[1:m + 1]


# exista      - exista succesor pe nivelul curent
# este_valid  - valoarea asezata pe nivelul curent este valida
k = 1                                   # se incepe cu primul nivel
init(k)

while k > 0:                            # cat timp nu s-a revenit sub nivelul 1
    exista = True
    este_valid = False

    # se cauta pe nivelul curent prima valoare care se accepta
    while exista and not este_valid:
        exista = succesor(k)
        if exista:
            este_valid = valid(k)

    if exista:
        if solutie(k):
            tipar()                   # configuratie intreaga
        else:
            k += 1                      # se coboara pe nivelul urmator,
            init(k)                     # care isi ia valorile de la capat
    else:
        k -= 1                          # valorile s-au terminat: revenire

if cel_mai_mare == -1:
    print("nu exista")
else:
    print("Cea mai scumpa alegere:", *best[1:m + 1], "-", cel_mai_mare, "lei")

Generarea combinărilor a fost cerută la Titularizare 2026, subiectul I. Rezolvarea întreagă, cu baremul pe puncte, este aici.

Submulțimi

Definiția matematică

Fie A o mulțime cu n elemente. Mulțimea tuturor submulțimilor lui A se numește mulțimea părților lui A și se notează P(A). Ea cuprinde și mulțimea vidă, și mulțimea A însăși.

Numărul submulțimilor unei mulțimi cu n elemente este

|P(A)| = 2ⁿ

Formula se obține din regula produsului: pentru fiecare dintre cele n elemente se hotărăște, separat de celelalte, dacă intră sau nu în submulțime. Fiecare element dă două posibilități, iar alegerile fiind independente, numărul submulțimilor este 2 · 2 · … · 2, cu n factori.

Aceeași numărare se poate face și după numărul de elemente: submulțimile cu exact m elemente sunt în număr de C(n,m), iar adunându-le pentru m de la 0 la n se obține tot 2ⁿ.

Fiecărei submulțimi îi corespunde vectorul ei caracteristic: șirul de n cifre binare în care cifra de pe poziția i este 1 dacă elementul i aparține submulțimii și 0 dacă nu aparține. Corespondența este bijectivă, deci numărul submulțimilor este numărul șirurilor binare de lungime n. Pe această corespondență se bazează și algoritmul de generare.

Pentru n = 3, cele 2³ = 8 submulțimi ale mulțimii {1, 2, 3} sunt:

{ }   {1}   {2}   {3}   {1,2}   {1,3}   {2,3}   {1,2,3}

Cum se construiește soluția

Submulțimile sunt combinări cu un număr variat de elemente, așa că nu se mai poate lucra cu m fixat. Se folosește vectorul caracteristic: nivelul k este chiar elementul k al mulțimii, iar st[k] spune dacă elementul intră în submulțime.

Pe fiecare nivel se încearcă două valori:

• st[k] = 0 — elementul k nu intră în submulțime;
• st[k] = 1 — elementul k intră în submulțime.

Ca prima valoare încercată să fie 0, init() pune în st[k] valoarea −1, iar succesor() merge până la 1. Nu există nicio restricție de respectat, deci valid() întoarce mereu 1. Soluția este completă la nivelul n, când s-a hotărât pentru fiecare element dacă intră sau nu.

La afișare se scriu numai elementele pentru care st[i] este 1. Pentru soluția în care toate valorile sunt 0 se afișează mulțimea vidă.

Exemplificarea etapelor

Pentru n = 3, cele 2³ = 8 submulțimi se obțin în ordinea de mai jos. Coloana din mijloc este chiar vectorul st: