#include <vector> #include <iostream> using namespace std; int n; // Половина длины vector<char> ans; // Наш ответ void rec(int balance) { if (ans.size() == 2 * n) { // Если выполняется - значит, мы закончили for (int i = 0; i < 2 * n; i++) cout << ans[i] << " "; cout << "\n"; } if (ans.size() + balance + 2 <= n * 2) { // Проверяем, успеем ли мы закрыть новую открывающую скобку // А теперь следите за руками: нам не нужно делать отдельный вектор для каждой последовательности ans.push_back('('); rec(balance + 1); ans.pop_back(); // Чтобы это понять, нужно осознавать рекурсию. Вначале мы добавляем в вектор скобку, а потом выполняем весь этот код снова. // То есть опять добавляем скобку, если можем. // И так будет происходить, пока мы не начнём из рекурсии выходить - то есть, пока мы не дойдём до нужной длины. // Тогда скобки начнут удаляться. Если вы это поняли - я вас поздравляю, вы классный(ая). } if (balance > 0) { // Если можем закрыть какую-то скобку - закрываем. ans.push_back(')'); rec(balance - 1); ans.pop_back(); } } int main() { cin >> n; rec(0); return 0; }
Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы.
x
х
Ваша же задача - реализовать алгоритм перебора.
Входные данные На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)).
Выходные данные Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.
x+1
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач