[Algorytmy] Wypisywanie nawiasów

[gmore]

Oto zadanie:
Napisz funkcję, która dla danej liczby naturalnej \(\displaystyle{ n}\) wypisze wszystkie poprawne ciągi nawiasów \(\displaystyle{ (,)}\) o łącznej długości \(\displaystyle{ 2 \cdot n}\).( poprawne czyli na przykład \(\displaystyle{ ((()));()()();(()())}\)). Widzę, że kążdy taki ciąg możemy opisać ciągiem zero-jedynkowym zaczynającym się od zera i takim, że w jeśli utniemy ciąg do \(\displaystyle{ k}\) pierwszych wyrazów to zawsze \(\displaystyle{ liczba zer \ge liczba jedynek}\) (dla dowolnego naturalnego k ), no i dodatkowo musi być tyle samo zer i jedynek. Jak teraz przejść do wypisywania takich kombinacji?

[matinf]

Najprościej jest rekurencyjnie, ale czy najwydajniej - zapewne nie.

Po prostu utrzymuj obecny ciąg, obecną sumę (liczbę jedynek).

Czyli coś w stylu:

Kod: Zaznacz cały

nawiasy (int suma, string ciag, int dlugosc){
  if (suma < 0 || ciag.length() > dlugosc){
        return;
    }
   if (suma == 0 && ciag.length() == dlugosc){
        print (ciag);
   }
   nawiasy (suma + 1, ciag + "(", dlugosc);
   nawiasy (suma - 1, ciag + ")", dlugosc);
}

nawiasy (0, "", 2  * n);