Combinări — AlgoClar

De ce contează?

Dintr-o echipă de 5 jucători trebuie să alegi 3 pentru un interviu. Nu contează ordinea în care îi alegi — e aceeași alegere ca . Numărul de astfel de alegeri sunt combinările: submulțimi de mărime fixă, fără ordine.

Ce este o combinare

O combinare de k elemente din n e o submulțime de mărime exact k, în care ordinea nu contează. și sunt aceeași combinare.

Numărul lor e C(n, k) („combinări de n luate câte k"). Pentru n=4, k=2: , , , , , — adică 6 = C(4,2).

Trucul: generezi crescător

Ca să nu generezi aceeași combinare în mai multe ordini, impui ca elementele alese să fie strict crescătoare. Următorul element pornește mereu de la start = ultimul + 1.

#include <iostream>
using namespace std;

int n, k;
int sol[20];

void genereaza(int pas, int start) {
    if (pas == k) {                 // am ales k elemente
        for (int i = 0; i < k; i++) cout << sol[i] << " ";
        cout << "\n";
        return;
    }
    for (int val = start; val <= n; val++) {    // doar valori > ultima
        sol[pas] = val;
        genereaza(pas + 1, val + 1);            // urmatorul porneste de la val+1
    }
}

int main() {
    n = 4; k = 2;
    genereaza(0, 1);    // 12 13 14 23 24 34
    return 0;
}

Observația-cheie

Cheia e genereaza(pas + 1, val + 1): următorul element pornește după cel curent. Asta garantează ordine crescătoare, deci fiecare combinare apare exact o dată — nu și pe lângă .

Combinări = submulțimi de mărime k

O combinare e o submulțime cu exact k elemente. Dacă ai genera toate submulțimile (2ⁿ) și ai păstra doar pe cele de mărime k, ai obține combinările — dar generarea crescătoare e mai eficientă, fiindcă nu produce risipă.

Optimizare: oprire devreme

Dacă au mai rămas mai puține elemente disponibile decât poziții de completat, nu mai are rost să continui pe acea ramură:

// daca de la `start` la n sunt mai putin de (k - pas) valori, abandoneaza
for (int val = start; val <= n - (k - pas) + 1; val++) { ... }

Complexitate

Operație	Timp
generarea tuturor combinărilor	O(C(n,k) · k)

C(n,k) poate fi mare, dar mult mai mic decât 2ⁿ pentru k apropiat de extreme.

Greșeli frecvente

Capcane reale la combinări:

Nu impui ordinea crescătoare: generezi și ca distincte → duplicate.
start greșit: dacă pornești următorul de la start în loc de val + 1, repeți elemente sau dublezi combinări.
Confuzi cu aranjamentele: la combinări ordinea nu contează; dacă o numeri, calculezi aranjamente.
Uiți cazul de bază pas == k: generezi submulțimi de orice mărime, nu exact k.

De reținut

Combinare = submulțime de k elemente, ordinea nu contează; C(n,k) combinări.
Generezi crescător: următorul element pornește de la val + 1 → fără duplicate.
Diferă de aranjamente (acolo ordinea contează); poți tăia ramurile fără destule elemente.