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

Generating balanced parentheses

Original: Generarea parantezărilor corecte

O(n)C++1753 lines1 example

The idea

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, ...

Original description (Romanian)

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, ...

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

Examples

Example 1

Input

3

Expected output

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

The code

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

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;
}

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