Recursion bracketed; or Dyck words generation We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…

A Dyck word is a string, of length 2n, consisting of n opening and n closing parentheses (( and )) fully matched (that is to say: for all prefixes of the string, the number of opening parentheses is greater than or equal to the number of closing ones).

It is interesting to note that the number of different Dyck words of length 2n is equal to the (n + 1)-th Catalan number.

It’s pretty straightforward to write a program that generates these words with a recursive function. But the goal here is to do the same thing without.

Challenge

Write a full program or function that takes a positive integer, n, using stdin or an acceptable alternative, and outputs all the different Dyck words of length 2n. The words can appear in any order and each must be separated from each other by a line break. Moreover, your program should not use recursive functions (see details below).

Rules


The output of your program should only contain Dyck words of length 2n, separated by line breaks. Each word must appear only once.
Your program must work at minimum for inputs 0 to 15.
You may not write recursive functions, neither direct (a function that calls itself) nor indirect (e.g. a function f that calls another function g that calls function f). That being said, you can still use the standard functions of your language without worry of how they work internally.
Similarly, your program should not call itself.
You may not use non-standard librairies.
Your program may not read or write files.
Your program must be able to run in a reasonable time for 0 ≤ n ≤ 15 (hence, naively generate all arrangements is probably not a good idea). Let’s say less than 20 minutes with a memory limit of 4 GB (my reference implementation in C manages n = 15 in less than 5 seconds).
All standard loopholes are forbidden.


As usual in code-golf, the shortest code in bytes wins. But if you have found an interesting way to achieve this challenge in your language, please do not hesitate.

Test I/O

For this input:

3


The output could be (any other order is correct too):

((()))
()()()
(()())
(())()
()(())
C99, 105 bytes



i,j,s;f(n){for(char a[31]={};++i%(1&lt;&lt;2*n);s||puts(a))for(j=s=0;~s&amp;&amp;j&lt;2*n;)s+=1-(a[j]=40+(i&gt;&gt;j++)%2)%2*2;}


Iterates over all strings of 2n parentheses.

With piped output and compiler flag -O3, input n = 15 takes roughly 15.5 seconds on my machine. Memory consumption is 1.2 MB.

Test it on Ideone.