#JavaScript (ES6), 203
Implementing this algorithm (point 3, totally iterative)
Within the limits of script executing in Firefox, I managed to have the 200K console output for input 12 in about 1.5 minutes
n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}
Less golfed
n=>{
b=[...Array(n)].map((_,i)=>1+2*i)
q=0
for(z=0;!z;)
{
c=[...'('.repeat(n+n)],
b.map(n=>c[n]=')'),
console.log(++q,c.join``)
for(z=i=n;i--&&z;)
if(b[i]<n+i)
for(z=0,b[j=i]++;++j<n-1;)
b[j]=Math.max(b[j-1],2*j)+1
}
}
Test generating all output but do not display it, just counting output rows
I got 90 sec for input 15
F=n=>{
for(b=[...Array(n)].map((_,i)=>1+2*i),z=0;!z;)
for(c=[...'('.repeat(n+n)],b.map(n=>c[n]=')'),console.log(c.join``),z=i=n;i--&&z;)
if(b[i]<n+i)for(z=0,b[j=i]++;++j<n-1;)b[j]=Math.max(b[j-1],2*j)+1
}
console.log=x=>o++ // console.log display no output, just count rows
function test() {
n=+I.value,o=0,t=+new Date
O.textContent='...wait...'
setTimeout(_=>(F(n),O.textContent=['rows='+o,'time sec '+(new Date-t)/1000]), 10)
}
test()
N:<input id=I value=12 type=number max=20><button onclick='test()'>go</button>
<pre id=O></pre>