Here is code to generate all sequences.

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
int n;string s;
bool check(int i,int bal)
{ return min(i,n-i)>=bal&&bal>=0; }
void tr(int i,int bal)
{ if(i==n){cout<<s<<"\n";return;}
  if(check(i+1,bal+1))
  {s+='(';tr(i+1,bal+1);s.pop_back();}
  if(check(i+1,bal-1))
  {s+=')';tr(i+1,bal-1);s.pop_back();}}
int main()
{ cin.tie(0)->sync_with_stdio(0);
  n=6;
  tr(0,0); }

To generate all bracket sequences, we call the tr function. $$$i$$$ is the number of characters in the prefix, and $$$bal$$$ is the balance of the prefix. The check function checks if there exists a bracket string where the prefix has the balance specified.

When we append an open parenthesis, the balance of the string increases by $$$1$$$. We check if there is at least one bracket string satisfying the prefix balance. If that string exists, we append an open parenthesis to the string and recurse. Then we remove the open parenthesis. Similarly for a close parenthesis, the balance decreases by $$$1$$$.

To check for the presence of a bracket string, consider a construction. $$$bal$$$ is the balance of the prefix. The balance is the count of open parentheses minus count of close parentheses. The balance of the whole bracket string is always $$$0$$$.

The balance of suffix is $$$0 - bal = -bal$$$.

We can calculate count of open parentheses in prefix = $$$(i+bal)/2$$$, count of close parentheses in prefix = $$$(i-bal)/2$$$, count of open parentheses in suffix = $$$(n-i-bal)/2$$$, count of close parentheses in suffix = $$$(n-i+bal)/2$$$.

These numbers must be nonnegative, also bal must be nonnegative. If they are nonnegative, there always exists a string satisfying the conditions.

We can shorten the conditions.

$$$(i+bal)/2>=0 \Rightarrow i>=-bal$$$

$$$(i-bal)/2>=0 \Rightarrow i>=bal$$$

$$$(n-i+bal)/2>=0 \Rightarrow n-i>=-bal$$$

$$$(n-i-bal)/2>=0 \Rightarrow n-i>=bal$$$

bal>=0 already implies i>=-bal and n-i>=-bal. We only have two conditions left.

$$$i>=bal$$$

$$$n-i>=bal$$$

Combining them, we have $$$\min(i,n-i)>=bal$$$. That's why the check function is just $$$bal>=0\text{&&}\min(n-i)>=bal$$$.

We first put $$$bal$$$ open parentheses at the beginning of string as well as bal close parentheses at the end of string.

The prefix has $$$i$$$ characters, after putting open parentheses in prefix we have $$$i-bal$$$ characters. We make a string that looks like (((()))) and put it in the remaining characters of prefix.

The number of open as well as close parentheses in that string is $$$(i-bal)/2$$$.

In total, open parenthesis count in prefix is $$$(i-bal)/2+bal=(i+bal)/2$$$, close parenthesis count in prefix is $$$(i-bal)/2$$$.

The suffix has $$$n-i$$$ characters, after putting close parentheses in suffix we have $$$n-i-bal$$$ characters. We also put something like (((()))) in the remaining characters.

Open and close parenthesis count in the string we put is $$$(n-i-bal)/2$$$.

Total count of open parentheses = $$$(n-i-bal)/2$$$, close = $$$(n-i-bal)/2+bal=(n-i+bal)/2$$$. The construction looks like ((((((())))((((()))))))). It is always balanced.

Here is code to generate random string.

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
int n;string s;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
bool check(int i,int bal)
{ return min(i,n-i)>=bal&&bal>=0; }
int main()
{ cin.tie(0)->sync_with_stdio(0);
  n=30;
  int bal=0;
  FOR(i,0,n-1)
  { bool open=check(i+1,bal+1),close=check(i+1,bal-1);
    if(open&&close)
    { if(rng()&1)
      { s+='(';bal++; }
      else{ s+=')';bal--; } }
    else if(open)
    { s+='(';bal++; }
    else{ s+=')';bal--; } }
  cout<<s; }

We check if we can append an open and close parenthesis. If we can append both, choose randomly.