Clasa a XI-a · Metoda backtrackingRead in English

Generarea parantezărilor corecte în C++

În engleză: Generating balanced parentheses

O(n)C++1753 de linii1 exemplu

Ideea

Afișează, în ordine lexicografică ('(' înaintea lui ')'), toate șirurile corecte formate din n perechi de paranteze rotunde. Ținem numărul de paranteze deschise și închise până acum: putem pune '(' dacă deschise < n și putem pune ')' doar dacă inchise < deschise (altfel am închide ceva ce nu e deschis). Numărul soluțiilor este numărul lui Catalan: 1, 2, 5, 14, 42, ...

Descrierea în engleză

Prints, in lexicographic order ('(' before ')'), all balanced strings made of n pairs of round brackets. We keep the number of brackets opened and closed so far: we may place '(' if opened < n and ')' only if closed < opened (otherwise we would close something that is not open). The number of solutions is the Catalan number: 1, 2, 5, 14, 42, ...

Complexitate
O(Catalan(n) · n) timp, O(n) memorie
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

3

Ieșire așteptată

((()))
(()())
(())()
()(())
()()()

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

paranteze-corecte.cpp
/*
 * Titlu: Generarea parantezărilor corecte
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează, în ordine lexicografică ('(' înaintea lui ')'), toate șirurile
 *            corecte formate din n perechi de paranteze rotunde. Ținem numărul de paranteze
 *            deschise și închise până acum: putem pune '(' dacă deschise < n și putem
 *            pune ')' doar dacă inchise < deschise (altfel am închide ceva ce nu e deschis).
 *            Numărul soluțiilor este numărul lui Catalan: 1, 2, 5, 14, 42, ...
 * Complexitate: O(Catalan(n) · n) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 3
 * Ieșire:
 * ((()))
 * (()())
 * (())()
 * ()(())
 * ()()()
 */
#include <iostream>
using namespace std;

int n;
char x[50];

void back(int k, int deschise, int inchise)
{
    if (k == 2 * n)
    {
        x[k] = 0;
        cout << x << '\n';
        return;
    }
    if (deschise < n)
    {
        x[k] = '(';
        back(k + 1, deschise + 1, inchise);
    }
    if (inchise < deschise)
    {
        x[k] = ')';
        back(k + 1, deschise, inchise + 1);
    }
}

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

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.