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

Generating subsets

Original: Generarea submulțimilor

ExponentialC++1753 lines1 example

The idea

Prints all non-empty subsets of the set {1, ..., n}, in lexicographic order. The elements of a subset are placed in strictly increasing order (as with combinations), but every partial solution is also a solution: we print it right away, then try to extend it. There are 2^n subsets, including the empty set (which is not printed here).

Original description (Romanian)

Afișează toate submulțimile nevide ale mulțimii {1, ..., n}, în ordine lexicografică. Elementele unei submulțimi se pun în ordine strict crescătoare (ca la combinări), dar fiecare soluție parțială este și ea o soluție: o afișăm imediat, apoi încercăm s-o prelungim. Există 2^n submulțimi, inclusiv mulțimea vidă (care aici nu se afișează).

Complexity
O(2^n · n) timp, O(n) memorie
Grade
Grade 11 (Clasa a XI-a)

Examples

Example 1

Input

3

Expected output

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

The code

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

submultimi.cpp
/*
 * Titlu: Generarea submulțimilor
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează toate submulțimile nevide ale mulțimii {1, ..., n}, în ordine
 *            lexicografică. Elementele unei submulțimi se pun în ordine strict crescătoare
 *            (ca la combinări), dar fiecare soluție parțială este și ea o soluție: o afișăm
 *            imediat, apoi încercăm s-o prelungim. Există 2^n submulțimi, inclusiv
 *            mulțimea vidă (care aici nu se afișează).
 * Complexitate: O(2^n · n) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 3
 * Ieșire:
 * 1
 * 1 2
 * 1 2 3
 * 1 3
 * 2
 * 2 3
 * 3
 */
#include <iostream>
using namespace std;

int n, x[25];

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

void back(int poz)
{
    for (int v = x[poz - 1] + 1; v <= n; v++)
    {
        x[poz] = v;
        afiseaza(poz);
        back(poz + 1);
    }
}

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

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