Grade 11 · BacktrackingCitește în română

Generating combinations

Original: Generarea combinărilor

O(n)C++1760 lines1 example

The idea

Prints all k-element subsets of the set {1, ..., n} (combinations of n taken k at a time). To avoid getting the same subset several times, the elements are generated in strictly increasing order: at position poz we try only values greater than x[poz - 1] and at most n - (k - poz), so there is still room for the next elements. Their number is C(n, k) = n! / (k! · (n - k)!).

Original description (Romanian)

Afișează toate submulțimile cu k elemente ale mulțimii {1, ..., n} (combinări de n luate câte k). Ca să nu obținem aceeași submulțime de mai multe ori, elementele se generează în ordine strict crescătoare: pe poziția poz încercăm doar valori mai mari decât x[poz - 1] și cel mult n - (k - poz), ca să mai rămână loc pentru elementele următoare. Numărul lor este C(n, k) = n! / (k! · (n - k)!).

Complexity
O(C(n, k) · k) timp, O(k) memorie
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

4 2

Expected output

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

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

combinari.cpp
/*
 * Titlu: Generarea combinărilor
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează toate submulțimile cu k elemente ale mulțimii {1, ..., n}
 *            (combinări de n luate câte k). Ca să nu obținem aceeași submulțime de mai
 *            multe ori, elementele se generează în ordine strict crescătoare: pe poziția
 *            poz încercăm doar valori mai mari decât x[poz - 1] și cel mult n - (k - poz),
 *            ca să mai rămână loc pentru elementele următoare. Numărul lor este
 *            C(n, k) = n! / (k! · (n - k)!).
 * Complexitate: O(C(n, k) · k) timp, O(k) memorie
 *
 * Exemplu
 * Intrare: 4 2
 * Ieșire:
 * 1 2
 * 1 3
 * 1 4
 * 2 3
 * 2 4
 * 3 4
 */
#include <iostream>
using namespace std;

int n, k, x[20];

void afiseaza()
{
    for (int i = 1; i <= k; i++)
    {
        cout << x[i] << ' ';
    }
    cout << '\n';
}

void back(int poz)
{
    // x[0] = 0, deci pe prima poziție pornim de la 1
    for (int v = x[poz - 1] + 1; v <= n - (k - poz); v++)
    {
        x[poz] = v;
        if (poz == k)
        {
            afiseaza();
        }
        else
        {
            back(poz + 1);
        }
    }
}

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

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.