brackets sequence dp

#include<bits/stdc++.h>
using namespace std;
const int MX=3e3+5;
typedef long long ll;
int dp[MX][MX],n;
int solve(int O,int C)
{
    if(O+C==n)return C==O;
    int& ans=dp[O][C];
    if(ans!=-1)return ans;
    ans=0;
    if(O>C)ans+=solve(O,C+1);
    ans+=solve(O+1,C);
    return ans;
}
string ans;
void findall(int O,int C)
{
    if(O+C==n)
    {
        cout<<ans<<'\n';
        return;
    }
    if(solve(O+1,C)>0)
    {
        ans.push_back('(');
        findall(O+1,C);
        ans.pop_back();
    }
    if(O>C&&solve(O,C+1)>0)
    {
        ans.push_back(')');
        findall(O,C+1);
        ans.pop_back();
    }

}
int main()
{

    while(cin>>n)
    {
     memset(dp,-1,sizeof dp);
        cout<<solve(0,0)<<'\n';
        findall(0,0);
    }
    return 0;
}