#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
using std::string;

struct Check {
    const char *text; int len; char* mask;
    typedef std::set<string> variants_t;
    typedef variants_t::iterator variants_it;
    variants_t variants;
    
    int check() {
        int level=0,rm_close=0,i,r2=0; char c;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { if (level>0) level--; else { rm_close++; mask[i]=c; } }
        }
        for(int l2=0;i>=0;i--) {
            c=text[i];        
            if (c==')') l2++;
            if (c=='(') { if (l2>0) l2--; else { r2++; mask[i]=c; } }
        }
        if (rm_close || level) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n %s\n\n",text,rm_close,level,mask);
        return rm_close+level;
    }
    void insert() {
        string s; for(int i=0;i<len;i++) if (text[i]!=mask[i]) s+=text[i];
        variants.insert(s);
    }
    void right(int pos) {
        insert();
        while(pos>=0 && mask[pos]!='(') pos--; if (pos<0) return;
        char type=mask[pos]; mask[pos]=' ';
        for(int i=pos+1;i<len;i++) {
            if (mask[i]==' ' && text[i]==type) {
                mask[i]=type;
                right(i-1);
                mask[i]=' ';
            }
        }
        mask[pos]=type;
    }
    void left(int pos) {
        right(len-1);
        while(pos<len && mask[pos]!=')') pos++; if (pos>=len) return;
        char type=mask[pos]; mask[pos]=' ';
        for(int i=pos-1;i>=0;i--) {
            if (mask[i]==' ' && text[i]==type) {
                mask[i]=type;
                left(pos+1);
                mask[i]=' ';
            }
        }
        mask[pos]=type;
    }
    void find() {
        variants.clear();
        left(0);
    }
    void show_variants() {
        int i=0; find();
        for(variants_it it=variants.begin();it!=variants.end();++it) {
            printf("%-6d%s\n",++i,it->c_str());
        }
    }
};

int main(int argc,char** argv) {
    enum { mask_max=64 }; char mask[mask_max];
    const char* list[]={
        "(a)())()))((b(b)",
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; 
        c.text=*s; c.len=strlen(*s);
        c.mask=mask; memset(mask,' ',c.len); mask[c.len]=0;
        if (c.check()) c.show_variants();
    }
    return 0;
}

"(a)())()))((b(b)" - 3 лишних ")" и 2 лишних "("
      )  ))((    

1     (a(()))(bb)
2     (a(()))b(b)
3     (a()())(bb)
4     (a()())b(b)
5     (a())()(bb)
6     (a())()b(b)
7     (a)(())(bb)
8     (a)(())b(b)
9     (a)()()(bb)
10    (a)()()b(b)

#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
using std::string;

struct Check {
    const char *text; int len, count; char* mask;
    typedef std::set<string> variants_t;
    typedef variants_t::iterator variants_it;
    variants_t variants;
    
    int check() {
        int level=0,rm_close=0,i,r2=0; char c;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { if (level>0) level--; else { rm_close++; mask[i]=c; } }
        }
        for(int l2=0;i>=0;i--) {
            c=text[i];        
            if (c==')') l2++;
            if (c=='(') { if (l2>0) l2--; else { r2++; mask[i]=c; } }
        }
        if (rm_close || level) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n %s\n\n",text,rm_close,level,mask);
        return rm_close+level;
    }
    void insert() {
        count++;
        string s; for(int i=0;i<len;i++) if (text[i]!=mask[i]) s+=text[i];
        variants.insert(s);
    }
    void right(int pos) {
        insert();
        for(;pos>=0;pos--) {
            while(pos>=0 && mask[pos]!='(') pos--; if (pos<0) return;
            char type=mask[pos]; mask[pos]=' '; int d=0;
            for(int i=pos+1;i<len && mask[i]!=type;i++) {
                if (mask[i]==' ' && text[i]==type) {
                    if (d) { mask[i]=type; right(i-1); mask[i]=' '; }
                } else d=1;
            }
            mask[pos]=type;
        }
    }
    void left(int pos) {
        right(len-1);
        for(;pos<len;pos++) {
            while(pos<len && mask[pos]!=')') pos++; if (pos>=len) return;
            char type=mask[pos]; mask[pos]=' '; int d=0;
            for(int i=pos-1;i>=0 && mask[i]!=type;i--) {
                if (mask[i]==' ' && text[i]==type) {
                    if (d) { mask[i]=type; left(pos+1); mask[i]=' '; }
                } else d=1;
            }
            mask[pos]=type;
        }
    }
    void find() {
        count=0;
        variants.clear();
        left(0);
    }
    void show_variants() {
        int i=0; find();
        for(variants_it it=variants.begin();it!=variants.end();++it) {
            printf("%-6d%s\n",++i,it->c_str());
        }
        int size=variants.size();
        printf("count=%d k=%.1f\n",count,(double)count/size);
    }
};

int main(int argc,char** argv) {
    enum { mask_max=128 }; char mask[mask_max];
    const char* list[]={
        "(a)())()))((b(b)",
        "()(())(()())((())()) ))))))(((((( ()(())(()())((())())",
        "())",
        "(())))",
        "((())))))",
        "(((())))))))",
        "((((())))))))))",
        "(((((())))))))))))",
        "((((((())))))))))))))",
        "(((((((())))))))))))))))",
        "((((((((()))))))))())))))))))",
        "(a(b(c(d(e(f(g(h(i)j)k)l)m)n)o)p)q)r)s)t)u)v)w)x)y)z)",
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; 
        c.text=*s; c.len=strlen(*s);
        c.mask=mask; memset(mask,' ',c.len); mask[c.len]=0;
        if (c.check()) c.show_variants();
    }
    return 0;
}

7     (a)()()(bb)
8     (a)()()b(b)
count=10 k=1.2
"()(())(()())((())()) ))))))(((((( ()(())(()())((())())" - 6 лишних ")" и 6 лишних "("
                      ))))))((((((                     
--
12749 ()(())(()())((())())(()())(()())((())())
12750 ()(())(()())((())())()(())(()())((())())
count=719104 k=56.4
"())" - 1 лишних ")" и 0 лишних "("
   )

1     ()
count=1 k=1.0
"(())))" - 2 лишних ")" и 0 лишних "("
     ))

1     (())
count=1 k=1.0
"((())))))" - 3 лишних ")" и 0 лишних "("
       )))

1     ((()))
count=1 k=1.0
"(((())))))))" - 4 лишних ")" и 0 лишних "("
         ))))

1     (((())))
count=1 k=1.0
"((((())))))))))" - 5 лишних ")" и 0 лишних "("
           )))))

1     ((((()))))
count=1 k=1.0
"(((((())))))))))))" - 6 лишних ")" и 0 лишних "("
             ))))))

1     (((((())))))
count=1 k=1.0
"((((((())))))))))))))" - 7 лишних ")" и 0 лишних "("
               )))))))

1     ((((((()))))))
count=1 k=1.0
"(((((((())))))))))))))))" - 8 лишних ")" и 0 лишних "("
                 ))))))))

1     (((((((())))))))
count=1 k=1.0
"((((((((()))))))))())))))))))" - 9 лишних ")" и 0 лишних "("
                     )))))))))
--
9     ((((((((())))))))())
10    ((((((((()))))))))()
count=512 k=51.2
"(a(b(c(d(e(f(g(h(i)j)k)l)m)n)o)p)q)r)s)t)u)v)w)x)y)z)" - 9 лишних ")" и 0 лишних "("
                                     ) ) ) ) ) ) ) ) )
--
48619 (a(b(c(d(e(f(g(h(ijklmnopq)rs)t)u)v)w)x)y)z)
48620 (a(b(c(d(e(f(g(h(ijklmnopqr)s)t)u)v)w)x)y)z)
count=48620 k=1.0

#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
using std::string;

struct Check {
    const char *text; int len, count; char* mask;
    typedef std::set<string> variants_t;
    typedef variants_t::iterator variants_it;
    variants_t variants;
    
    int check() {
        int level=0,rm_close=0,i,r2=0; char c;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { if (level>0) level--; else { rm_close++; mask[i]=c; } }
        }
        for(int l2=0;i>=0;i--) {
            c=text[i];        
            if (c==')') l2++;
            if (c=='(') { if (l2>0) l2--; else { r2++; mask[i]=c; } }
        }
        if (rm_close || level) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n %s\n\n",text,rm_close,level,mask);
        return rm_close+level;
    }
    void insert() {
        count++;
        string s; for(int i=0;i<len;i++) if (text[i]!=mask[i]) s+=text[i];
        variants.insert(s);
    }
    void right(int pos) {
        insert();
        for(;pos>=0;pos--) {
            while(pos>=0 && mask[pos]!='(') pos--; if (pos<0) return;
            char type=mask[pos]; mask[pos]=' '; 
            int i=pos+1;
            while(i<len && (mask[i]==' ' && text[i]==type)) i++; 
            for(;i<len && mask[i]!=type;i++) {
                if (mask[i]==' ' && text[i]==type) {
                    mask[i]=type; right(i-1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void left(int pos) {
        right(len-1);
        for(;pos<len;pos++) {
            while(pos<len && mask[pos]!=')') pos++; if (pos>=len) return;
            char type=mask[pos]; mask[pos]=' ';
            int i=pos-1;
            while(i>=0 && (mask[i]==' ' && text[i]==type)) i--; i++;
            for(;i>=0 && mask[i]!=type;i--) {
                if (mask[i]==' ' && text[i]==type) {
                    mask[i]=type; left(pos+1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void find() {
        count=0;
        variants.clear();
        left(0);
    }
    void show_variants() {
        int i=0; find();
        for(variants_it it=variants.begin();it!=variants.end();++it) {
            printf("%-6d%s\n",++i,it->c_str());
        }
        int size=variants.size();
        printf("count=%d k=%.1f\n",count,(double)count/size);
    }
};

int main(int argc,char** argv) {
    enum { mask_max=128 }; char mask[mask_max];
    const char* list[]={
        "(a)())()))((b(b)",
        "()(())(()())((())()) ))))))(((((( ()(())(()())((())())",
        "())",
        "(())))",
        "((())))))",
        "(((())))))))",
        "((((())))))))))",
        "(((((())))))))))))",
        "((((((())))))))))))))",
        "(((((((())))))))))))))))",
        "((((((((()))))))))())))))))))",
        "(a(b(c(d(e(f(g(h(i)j)k)l)m)n)o)p)q)r)s)t)u)v)w)x)y)z)",
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; 
        c.text=*s; c.len=strlen(*s);
        c.mask=mask; memset(mask,' ',c.len); mask[c.len]=0;
        if (c.check()) c.show_variants();
    }
    return 0;
}

g++ a.cpp && ./a.out | grep -A 2 -B 2 count
9     (a)()()(bb)
10    (a)()()b(b)
count=38 k=3.8
"()(())(()())((())()) ))))))(((((( ()(())(()())((())())" - 6 лишних ")" и 6 лишних "("
                      ))))))((((((                     
--
12749 ()(())(()())((())())(()())(()())((())())
12750 ()(())(()())((())())()(())(()())((())())
count=3068064 k=240.6
"())" - 1 лишних ")" и 0 лишних "("
   )

1     ()
count=2 k=2.0
"(())))" - 2 лишних ")" и 0 лишних "("
     ))

1     (())
count=4 k=4.0
"((())))))" - 3 лишних ")" и 0 лишних "("
       )))

1     ((()))
count=8 k=8.0
"(((())))))))" - 4 лишних ")" и 0 лишних "("
         ))))

1     (((())))
count=16 k=16.0
"((((())))))))))" - 5 лишних ")" и 0 лишних "("
           )))))

1     ((((()))))
count=32 k=32.0
"(((((())))))))))))" - 6 лишних ")" и 0 лишних "("
             ))))))

1     (((((())))))
count=64 k=64.0
"((((((())))))))))))))" - 7 лишних ")" и 0 лишних "("
               )))))))

1     ((((((()))))))
count=128 k=128.0
"(((((((())))))))))))))))" - 8 лишних ")" и 0 лишних "("
                 ))))))))

1     (((((((())))))))
count=256 k=256.0
"((((((((()))))))))())))))))))" - 9 лишних ")" и 0 лишних "("
                     )))))))))
--
9     ((((((((())))))))())
10    ((((((((()))))))))()
count=19683 k=1968.3
"(a(b(c(d(e(f(g(h(i)j)k)l)m)n)o)p)q)r)s)t)u)v)w)x)y)z)" - 9 лишних ")" и 0 лишних "("
                                     ) ) ) ) ) ) ) ) )
--
48619 (a(b(c(d(e(f(g(h(ijklmnopq)rs)t)u)v)w)x)y)z)
48620 (a(b(c(d(e(f(g(h(ijklmnopqr)s)t)u)v)w)x)y)z)
count=155382 k=3.2

#include <stdio.h>
#include <string.h>
#include <set>
#include <string>
using std::string;

struct Check {
    const char *text; int len, count; char* mask;
    typedef std::set<string> variants_t;
    typedef variants_t::iterator variants_it;
    variants_t variants;
    
    int check() {
        int level=0,rm_close=0,i,r2=0; char c;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { if (level>0) level--; else { rm_close++; mask[i]=c; } }
        }
        for(int l2=0;i>=0;i--) {
            c=text[i];        
            if (c==')') l2++;
            if (c=='(') { if (l2>0) l2--; else { r2++; mask[i]=c; } }
        }
        if (rm_close || level) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n %s\n\n",text,rm_close,level,mask);
        return rm_close+level;
    }
    void insert() {
        count++;
        string s; for(int i=0;i<len;i++) if (mask[i]==' ') s+=text[i];
        variants.insert(s);
    }
    void right(int pos) {
        insert();
        for(;pos>=0;pos--) {
            while(pos>=0 && mask[pos]!='(') pos--; if (pos<0) return;
            char type=mask[pos]; mask[pos]=' '; 
            int i=pos+1;
            for(int j=i;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; i=j+1; }
            for(;i<len && mask[i]!=type;i++) {
                if (mask[i]==' ' && text[i]==type) {
                    for(int j=i+1;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; i=j; }
                    mask[i]=type; right(i-1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void left(int pos) {
        right(len-1);
        for(;pos<len;pos++) {
            while(pos<len && mask[pos]!=')') pos++; if (pos>=len) return;
            char type=mask[pos]; mask[pos]=' ';
            int i=pos-1;
            for(int j=i;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; i=j-1; }
            for(;i>=0 && mask[i]!=type;i--) {
                if (mask[i]==' ' && text[i]==type) {
                    for(int j=i-1;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; i=j; }
                    mask[i]=type; left(pos+1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void shift() {
        char type=')';
        for(int i=1;i<len;i++) {
            if (mask[i]==type) {
                int k=i; for(int j=i-1;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; k=j; }
                mask[i]=' '; mask[k]=type;
            }
        }
        type='(';
        for(int i=len-2;i>=0;i--) {
            if (mask[i]==type) {
                int k=i; for(int j=i+1;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; k=j; }
                mask[i]=' '; mask[k]=type;
            }
        }
    }
    void find() {
        count=0;
        variants.clear();
        shift();
        left(0);
    }
    void show_variants() {
        int i=0; find();
        for(variants_it it=variants.begin();it!=variants.end();++it) {
            printf("%-6d%s\n",++i,it->c_str());
        }
        int size=variants.size();
        printf("count=%d k=%.1f%s\n",count,(double)count/size,count!=size ? " PROBLEM":"");
    }
};

int main(int argc,char** argv) {
    enum { mask_max=128 }; char mask[mask_max];
    const char* list[]={
        "(a)())()))((b(b)",
        "()(())(()())((())()) ))))))(((((( ()(())(()())((())())", 
        "())",
        "(())))",
        "((())))))",
        "(((())))))))",
        "((((())))))))))",
        "(((((())))))))))))",
        "((((((())))))))))))))",
        "(((((((())))))))))))))))",
        "((((((((()))))))))())))))))))",
        "(a(b(c(d(e(f(g(h(i)j)k)l)m)n)o)p)q)r)s)t)u)v)w)x)y)z)",
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; 
        c.text=*s; c.len=strlen(*s);
        c.mask=mask; memset(mask,' ',c.len); mask[c.len]=0;
        if (c.check()) c.show_variants();
    }
    return 0;
}

count=10 k=1.0
count=58566 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=1 k=1.0
count=10 k=1.0
count=48620 k=1.0

#include <stdio.h>
#include <string.h>

struct Check {
    const char *text; int len, count; char* mask;
    
    int check() {
        int level=0,rm_close=0,i,r2=0; char c;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { if (level>0) level--; else { rm_close++; mask[i]=c; } }
        }
        for(int l2=0;i>=0;i--) {
            c=text[i];        
            if (c==')') l2++;
            if (c=='(') { if (l2>0) l2--; else { r2++; mask[i]=c; } }
        }
        if (rm_close || level) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n",text,rm_close,level);
        return rm_close+level;
    }
    void print() {
        printf("%-6d ",++count);
        for(int i=0;i<len;i++) if (mask[i]==' ') printf("%c",text[i]);
        //printf(" - |%s|",mask);
        printf("\n");
    }
    void right(int pos) {
        print();
        for(;pos>=0;pos--) {
            while(pos>=0 && mask[pos]!='(') pos--; if (pos<0) return;
            char type=mask[pos]; mask[pos]=' '; 
            int i=pos+1;
            for(int j=i;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; i=j+1; }
            for(;i<len && mask[i]!=type;i++) {
                if (mask[i]==' ' && text[i]==type) {
                    for(int j=i+1;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; i=j; }
                    mask[i]=type; right(i-1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void left(int pos) {
        right(len-1);
        for(;pos<len;pos++) {
            while(pos<len && mask[pos]!=')') pos++; if (pos>=len) return;
            char type=mask[pos]; mask[pos]=' ';
            int i=pos-1;
            for(int j=i;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; i=j-1; }
            for(;i>=0 && mask[i]!=type;i--) {
                if (mask[i]==' ' && text[i]==type) {
                    for(int j=i-1;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; i=j; }
                    mask[i]=type; left(pos+1); mask[i]=' ';
                }
            }
            mask[pos]=type;
        }
    }
    void ground_state() {
        char type=')';
        for(int i=1;i<len;i++) {
            if (mask[i]==type) {
                int k=i; for(int j=i-1;j>=0;j--) { if (mask[j]!=' ' || text[j]!=type) break; k=j; }
                mask[i]=' '; mask[k]=type;
            }
        }
        type='(';
        for(int i=len-2;i>=0;i--) {
            if (mask[i]==type) {
                int k=i; for(int j=i+1;j<len;j++) { if (mask[j]!=' ' || text[j]!=type) break; k=j; }
                mask[i]=' '; mask[k]=type;
            }
        }
    }
    void show_variants() {
        ground_state();
        count=0; left(0);
        printf("variants count=%d\n",count);
    }
};

int main(int argc,char** argv) {
    enum { mask_len=128 }; char mask[mask_len+1];
    const char* list[]={
        "(a)())()))((b(b)",
        argc>1 ? argv[1] : 0,
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; 
        c.text=*s; c.len=strlen(c.text); if (c.len>mask_len) continue;
        c.mask=mask; memset(mask,' ',c.len); mask[c.len]=0;
        if (c.check()) c.show_variants();
    }
    return 0;
}

"(a)())()))((b(b)" - 3 лишних ")" и 2 лишних "("
1      (a)()()b(b)
2      (a)()()(bb)
3      (a())()b(b)
4      (a())()(bb)
5      (a()())b(b)
6      (a()())(bb)
7      (a(()))b(b)
8      (a(()))(bb)
9      (a)(())b(b)
10     (a)(())(bb)
variants count=10

#include <iostream>
#include <set>
#include <string>

void remove_redundant_opening_brackets(const std::string& s, size_t end, std::set<std::string>& output)
{
   int level = 0;
   for (size_t i = end; i--;)
   {
      if (s[i] == ')')
      {
         ++level;
      }
      else if (s[i] == '(' && --level < 0)
      {
         char last = 0;
         for (size_t j = i; j < s.length(); ++j)
         {
            if (s[j] == '(' && last != '(')
            {
               remove_redundant_opening_brackets(std::string(s).erase(j, 1), i, output);
            }
            last = s[j];
         }
         return;
      }
   }
   output.insert(s);
}

void remove_redundant_brackets(const std::string& s, size_t begin, std::set<std::string>& output)
{
   int level = 0;
   for (size_t i = begin; i < s.length(); ++i)
   {
      if (s[i] == '(')
      {
         ++level;
      }
      else if (s[i] == ')' && --level < 0)
      {
         char last = 0;
         for (size_t j = 0; j <= i; ++j)
         {
            if (s[j] == ')' && last != ')')
            {
               remove_redundant_brackets(std::string(s).erase(j, 1), i, output);
            }
            last = s[j];
         }
         return;
      }
   }
   remove_redundant_opening_brackets(s, s.length(), output);
}

std::set<std::string> remove_redundant_brackets(const std::string& s)
{
   std::set<std::string> output;
   remove_redundant_brackets(s, 0, output);
   return output;
}

int main()
{
   const auto s = "(a)())()))((b(b)";

   for (auto&& s : remove_redundant_brackets(s))
   {
      std::cout << s << std::endl;
   }
}

R>Ну вот, например, такое решение канает как красивое?

g++ aa.cpp && time ./a.out "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" | tail
681114 ()(())(()())(())((())(()))(((((()(((((()))))))))))
681115 ()(())(()())(())((())(()))(()(((())(()())((())))))
681116 ()(())(()())(())((())(()))((()((())(()())((())))))
681117 ()(())(()())(())((())(()))(()((())(()())((())())))
681118 ()(())(()())(())((())(()))((()(())(()())((())())))
681119 ()(())(()())(())((())(()))(()(())(()())((())(())))
681120 ()(())(()())(())((())(()))((()())(()())((())(())))
681121 ()(())(()())(())((())(()))(()())(()())((())(()()))
681122 ()(())(()())(())((())(()))((()))(()())((())(()()))
variants count=681122

real    0m0.602s
user    0m0.598s
sys    0m0.037s

R>>Ну вот, например, такое решение канает как красивое?

_>g++ aa.cpp && time ./a.out "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" | tail
_>681114 ()(())(()())(())((())(()))(((((()(((((()))))))))))
_>681115 ()(())(()())(())((())(()))(()(((())(()())((())))))
_>681116 ()(())(()())(())((())(()))((()((())(()())((())))))
_>681117 ()(())(()())(())((())(()))(()((())(()())((())())))
_>681118 ()(())(()())(())((())(()))((()(())(()())((())())))
_>681119 ()(())(()())(())((())(()))(()(())(()())((())(())))
_>681120 ()(())(()())(())((())(()))((()())(()())((())(())))
_>681121 ()(())(()())(())((())(()))(()())(()())((())(()()))
_>681122 ()(())(()())(())((())(()))((()))(()())((())(()()))
_>variants count=681122
_>

#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>

class RedundantBracketRemover
{
public:

   RedundantBracketRemover(const std::string& s)
   {
      remove_redundant_brackets(s, 0);
   }

   const std::vector<std::string>& get() const { return m_output; }

private:
   void remove_redundant_opening_brackets(const std::string& s, size_t end)
   {
      int balance = 0;
      for (size_t i = end; i--;)
      {
         if (s[i] == ')')
         {
            ++balance;
         }
         else if (s[i] == '(' && --balance < 0)
         {
            char last = 0;
            for (size_t j = i; j < s.length(); ++j)
            {
               if (s[j] == '(' && last != '(')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                     remove_redundant_opening_brackets(s2, i);
               }
               last = s[j];
            }
            return;
         }
      }
      m_output.push_back(s);
   }

   void remove_redundant_brackets(const std::string& s, size_t begin)
   {
      int balance = 0;
      for (size_t i = begin; i < s.length(); ++i)
      {
         if (s[i] == '(')
         {
            ++balance;
         }
         else if (s[i] == ')' && --balance < 0)
         {
            char last = 0;
            for (size_t j = 0; j <= i; ++j)
            {
               if (s[j] == ')' && last != ')')
               {
                  auto s2 = std::string(s).erase(j, 1);
                  if (m_nodes.insert(s2).second)
                  {
                     remove_redundant_brackets(s2, i);
                  }
               }
               last = s[j];
            }
            return;
         }
      }
      remove_redundant_opening_brackets(s, s.length());
   }
private:
   std::vector<std::string> m_output;
   std::unordered_set<std::string> m_nodes;
};

std::vector<std::string> remove_redundant_brackets(const std::string& s)
{
   return RedundantBracketRemover(s).get();
}

int main()
{
   const auto s = "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))";
   //const auto s = "(a)())()))((b(b)";

   auto variants = remove_redundant_brackets(s).size();
   std::cout << "variants: " << variants << std::endl;

//   for (auto&& s : remove_redundant_brackets(s))
//   {
//      std::cout << s << std::endl;
//   }
}

R>Ну так то ведь был просто эскиз безо всякой оптимизации. После самой косметической оптимизации у меня этот пример считается за 4 секунды (на ideone). Только количество вариантов у меня получается побольше, чем у тебя, а именно 966730. Кто-то из нас где-то налажал Могу выслать архивом мой аутпут, если хочешь.

// a3.cpp
#include <stdio.h>

struct Check {
    const char* text; int len;
    int *L,*R; int nl,nr, lim, count;
    int check() {
        int level, rm_close, rm_open,i; char c;
        nr=0; nl=0; L[0]=0; L[1]=0; R[0]=0; R[1]=0;
        level=0; rm_close=0; rm_open=0; c=0;
        for(i=0;c=text[i];i++) {
            if (c=='(') level++;
            if (c==')') { L[nl]++; if (level>0) level--; else { L[nl+1]++; rm_close++; } } 
            else { if (L[nl]) { nl+=2; if (nl+2>=lim) throw this; L[nl]=0; L[nl+1]=0; } }
        }
        rm_open=level; level=0; len=i;
        for(--i;i>=0;i--) {
            c=text[i];        
            if (c==')') level++;
            if (c=='(') { R[nr]++; if (level>0) level--; else R[nr+1]++; } 
            else { if (R[nr]) { nr+=2; if (nl+2>=lim) throw this; R[nr]=0; R[nr+1]=0; } }
        }
        if (!L[nl]) nl-=2; if (!R[nr]) nr-=2;
        if (rm_close || rm_open) printf("\"%s\" - %d лишних \")\" и %d лишних \"(\"\n",text,rm_close,rm_open);
        return rm_close+rm_open;
    }
    void show() {
        count++;
        //printf("%-6d ",count);
        for(int pl=0,pr=nr,i=0;i<len;i++) {
            int n=1; char c=text[i]; 
            if (c==')') { i+=L[pl]-1; n=L[pl]-L[pl+1]; pl+=2; }
            if (c=='(') { i+=R[pr]-1; n=R[pr]-R[pr+1]; pr-=2; }
            for(int j=0;j<n;j++) putchar(c);
        }
        putchar('\n');
    }
    void right(int p,int s=1) {
        if (s) show();
        while(p>=0 && R[p+1]==0) p-=2;
        if (p>=0) {
            int i=p-2; while(i>=0 && R[i+1]>=R[i]) i-=2;
            if (i>=0) { right(p-2,0); right_dec(p,i); }
        }    
    }
    void right_dec(int p,int i) {
        R[i+1]++; R[p+1]--; right(p-2);
        if (R[p+1]>0) {
            int j=i; while(j>=0 && R[j+1]>=R[j]) j-=2;
            if (j>=0) right_dec(p,j);
        }
        R[i+1]--; R[p+1]++;
    }    
    void left(int p,int s=1) {
        if (s) right(nr);
        while(p>=0 && L[p+1]==0) p-=2;
        if (p>=0) {
            int i=p-2; while(i>=0 && L[i+1]>=L[i]) i-=2;
            if (i>=0) { left(p-2,0); left_dec(p,i); }
        }    
    }
    void left_dec(int p,int i) {
        L[i+1]++; L[p+1]--; left(p-2);
        if (L[p+1]>0) {
            int j=i; while(j>=0 && L[j+1]>=L[j]) j-=2;
            if (j>=0) left_dec(p,j);
        }
        L[i+1]--; L[p+1]++;
    }
    void show_variants() {
        count=0; left(nl); 
        printf("count=%d\n",count);
    }
};

int main(int argc,char** argv) {
    enum { limit=128 };
    int L[limit],R[limit];
    const char* list[]={
        "(a)())()))((b(b)",
        //"()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))",
        argc>1 ? argv[1] : 0,
        0
    };
    for(const char** s=list;*s;s++) {
        Check c; c.L=L; c.R=R; c.lim=limit; c.text=*s;
        try { 
            if (c.check()) c.show_variants();
        } catch(Check*) {
            printf("limit exceeded - %s\n",*s);
        }
    }
    return 0;
}

length: 8
total: 5
        string #1: ((()))()
        string #2: (()())()
        string #3: (())()()
        string #4: ()(())()
        string #5: ()()()()

int length;
string line;
vector<vector<vector<int>>> cache;

int how_many(int position, int balance, int left)
{
    int &result = cache[position][balance][left];

    if (result != -1)
        return result;

    if (left == 0)
        return balance == 0;

    result = 0;
    for (int p = position; p < line.size(); ++p)
    {
        if (line[p] == '(')
        {
            result += how_many(p + 1, balance + 1, left - 1);
            break;
        }
    }

    for (int p = position; balance > 0 && p < line.size(); ++p)
    {
        if (line[p] == ')')
        {
            result += how_many(p + 1, balance - 1, left - 1);
            break;
        }
    }

    return result;
}

string get(string& answer, int position, int balance, int length, int k)
{
    if (length == 0)
        return answer;

    int result = 0;
    int p = position;
    for (; p < line.size(); ++p)
    {
        if (line[p] == '(')
        {
            result += how_many(p + 1, balance + 1, length - 1);
            break;
        }
    }

    if (k <= result)
    {
        answer.push_back('(');
        get(answer, p + 1, balance + 1, length - 1, k);
    }
    else
    {
        for (int p = position; balance > 0 && p < line.size(); ++p)
        {
            if (line[p] == ')')
            {
                answer.push_back(')');
                get(answer, p + 1, balance - 1, length - 1, k - result);
                break;
            }
        }
    }

    return answer;
}

string get(int k)
{
    string answer = "";
    return get(answer, 0, 0, length, k);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif 

    getline(cin, line);
    const int n = line.size();

    cache.assign(n + 1, vector<vector<int>>(n, vector<int>(n + 1, -1)));

    length = 0;

    for (int i = 0; i < n; i += 2)
    {
        int t = how_many(0, 0, i);
        if (t > 0)
            length = i;
    }

    int total = how_many(0, 0, length);

    cout << "length: " << length << endl;
    cout << "total: " << total << endl;

    for (int i = 1; i <= total; ++i)
    {
        string str = get(i);
        cout << "\tstring #" << i << ": " << str << endl;
    }
}

(a)())()))((b(b)
  l ll lLL
          RR r
L: 0/1 0/2 2/3
R: 0/1 2/2
count(L)=5
count(R)=2
5*2=10

()())()))((()
 l ll lLL
         RRr
L: 0/1 0/2 2/3
R: 2/3
count(L)=5
count(R)=1
5*1=5

дано Aij, bi
 y[i] = sum(A[i,j]*x[j],j=1..n) + b[i]  , i=1..n
 y[i]>=0, x[i]>= 0
найти x[i],y[i]