task91.cpp

#include <iostream>
#include <string>

std::string Initialize(unsigned short number)
{
	std::string sequence;
	sequence.reserve(2 * number);
	for (auto i = 0; i < number; ++i)
		sequence += '(';
	for (auto i = 0; i < number; ++i)
		sequence += ')';
	return sequence;
}

bool GenerateNext(std::string& sequence)
{
    const auto size = sequence.size();
    if (size % 2 != 0)
        return false;

    for (int i = size - 1, counter = 0; i >= 0; --i)
    {
        if (sequence[i] == ')')
            ++counter;
        else if (sequence[i] == '(')
        {
            --counter;
            if (counter <= 0)
                continue;
            
            // Найдена самая правая открывающая скобка - меняем ее на закрывающую с коррекцией счетчика
            --counter;
            sequence[i++] = ')';

            /* Далее формируем лексикографически следующую последовательность.
             * (size - i)	- все скобки справа от текущей, включая текущую,
             * counter		- число незакрытых на данный момент закрывающих скобок справа от текущей.
             * Тогда мы имеем P = (size - i - counter) пар скобок справа от текущей:
             * P/2 открывающих и P/2 закрывающих.
            */
            int open = (size - i - counter) / 2;
            int close = size - i - open;

            while (open--)
                sequence[i++] = '(';
            while (close--)
                sequence[i++] = ')';
            return true;
        }
    }
    return false;
}

int main()
{
    unsigned short number{ 0 };
    std::cin >> number;

    auto sequence = Initialize(number);
    do
    {
        std::cout << sequence << '\n';
    } while (GenerateNext(sequence));

    system("pause");
    return 0;
}