Recursion bracketed; or Dyck words generation

C99, 105 bytes

i,j,s;f(n){for(char a[31]={};++i%(1<<2*n);s||puts(a))for(j=s=0;~s&&j<2*n;)s+=1-(a[j]=40+(i>>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.

CJam (48 bytes)

ri"()"*${_p_,{1$>_)-,\(-,<},_{W=/(\s$1m>+}{&}?}h

Online demo. This effectively takes one obvious recursive solution and makes it iterative. Instead of actually simulating the steps back up the stack, it applies a successor rule:

Find the last ( which starts a suffix with strictly more ) than (; sort that suffix, and rotate once.

Note that this is deliberately designed to avoid keeping the full list of solutions in memory, because I don't think it fits (at least, not if run on a 64-bit machine. It might on a 32-bit machine). There are 9694845 Dyck paths for n=15, so that's 30*9694845 characters, and 92*9694845 = 891925740 bytes of memory just for the (Java) String objects. But then the List holding the objects probably wraps an array with space for 16777216 elements, which is a further 256MB, and the CJam interpreter itself seems to add quite a bit of overhead.

---

(42 bytes)

Ma{{_'(+\')+}%{"()"\f{\-,}I+_$=},}ri:I2**,

This builds the strings up one character at a time, filtering to ensure that no string has more than n opening parentheses or more closing than opening parentheses. However, it runs out of memory with 3GB for n=15.

The same idea at 39 bytes, but this runs out of memory earlier.

Ma{"()":Sm*::+{S\f{\-,}I+_$=},}ri:I2**`

Online demo

---

(24 bytes)

My original answer, now disqualified by rule changes.

{"()"*e!{0\+{~_}*]1&!},}

This is an anonymous function which takes input on the stack. Online demo.

It works by the obvious approach of taking all permutations of n pairs of parentheses and filtering for those which are balanced.

Pyth, 26 23 bytes

jeuaGsMs*VjRL`()_GGQ]]k

Try it online

                    ]]k   starting at G=[['']],
  u                Q      repeat the given number of times:
                _G          reversed G
          jRL`()            parenthesize each level-2 element
        *V        G         take Cartesian products of corresponding
                              elements of that and G
       s                    concatenate, yielding a list of pairs
     sM                     concatenate each resulting pair
   aG                       append the resulting list to G
je                        finally, join the last result on newlines

This directly follows the Catalan recurrence (with a non-recursive dynamic programming implementation) and doesn’t use any filtering. On my laptop, it runs in 55 seconds using 2.67 GiB RAM for n = 15.

Pyth, 33 bytes, O(n) memory

=S*Q`()Wn2J+3x
Q"(()"=+.<S<QJ1>QJ

Try it online

  *Q`()                  build a string with Q copies of "()"
 S                       sort it
=                        assign it to Q

       W                 while the following is true:
(newline)                  print Q
Q
             x             take the index of the first occurrence of "(()"
 "(()"
           +3              add 3
          J                assign to J
        n2                 is this not equal to 2 (i.e. was "(()" found)?
                         do the following:
           <QJ             take the first J characters of Q
          S                sort them
        .<    1            cyclically shift them left by 1
       +       >QJ         add the remaining characters of Q
      =                    assign to Q

This algorithm outputs all Dyck words in a stream, with each word being generated from the previous one and no additional state. On my laptop, it runs in 170 seconds using basically no RAM for n = 15.

As an example illustrating how it works:

()()()()((()()(())))(())
         ^^^               becomes
(((((()))))(()(())))(())

Similarly computing the words in the reverse of this order also takes 33 bytes:

=*QK`()WJhx
Q_K=+t.iFc2_<QJ+K>QhJ

Try it online