Generate all brace-strings of length n A brace string is defined as a string consisting of the characters *()[] in which braces match correctly:

[brace-string] ::= [unit] || [unit] [brace-string]
[unit]         ::= "" || "*" || "(" [brace-string] ")" || "[" [brace-string] "]"


This is a valid brace-string:

((())***[]**)****[(())*]*


But these are not:

)(
**(**[*](**)
**([*)]**


Your task is to write a program (or function) that, given a positive integer n, takes a number as input and outputs (or returns) all valid brace strings of length n.

Specifications


You may output the strings in any order.
You may output as a list or a string separated by a different character.
Your program must handle 0 correctly. There is 1 possible brace-string of length 0, which is the empty string "".
This is code-golf, so the shortest valid answer – measured in bytes – wins.


Test Cases

0. 
1. *
2. ** () []
3. *** ()* []* (*) [*] *() *[]
4. **** ()** []** (*)* [*]* (**) **() **[] *(*) *[*] (()) ()() ()[] ([]) [**] [()] [[]] []() [][] *()* *[]*
Prolog, 69 bytes

s--&gt;[];e,s.
e--&gt;&quot;*&quot;;&quot;(&quot;,s,&quot;)&quot;;&quot;[&quot;,s,&quot;]&quot;.
b(N,A):-length(A,N),s(A,[]).

One of the most interesting properties of Prolog is that in many cases it's capable of running a program backwards; for example, instead of testing to see if something's true, you can generate all solutions for which it's true, and instead of checking the length of a string, you can generate all strings with a given length. (Another nice property of Prolog is that it requires whitespace after the end of each predicate definition, and a newline can be inserted as cheaply as a space; thus even golfed programs are often fairly readable.)
The above defines a predicate (the equivalent of a function) b which tests to see if a string has a given length and is a &quot;brace string&quot; as defined in the question. Specifically, it does this via Prolog's grammar/regex/pattern-match support that gives some nice, short sugar for defining this sort of expression (apparently this is standard/portable, but I was unaware of this while originally writing the answer, and thus assumed the answer would work on only one Prolog implementation; it seems it works on every implementation that complies with the standards, though). The program can be translated into English fairly directly; the first two lines say &quot;an s is an empty string, or an e followed by an s; an e is an asterisk, or an s in parentheses, or an s in square brackets&quot;. The third line can be interpreted as &quot;The b of N can be A if A is a list with length N and A is an s followed by a null string.&quot;
I took some care to write s (and thus b) so that they match each &quot;brace string&quot; in exactly one way (which is the reason that both s and e have to exist, rather than grouping them into one predicate). This makes them both entirely reversible; thus b can be used to generate all &quot;brace strings&quot; of a given length, in addition to testing if a string is a brace string of a given length (it can also be used a third way round, to figure out the length of a brace string, but that is almost certainly its least useful mode of operation). The implementation is recursive, e.g. to generate an s, the code will generate all possible es that are no longer than the required length of the output, and append all possible ss that fit in the remaining space to them; because I specified the length of the argument in advance (within b), the Prolog engine knows that it can't generate output that's longer than the given length, which allows the recursion to terminate.
Here's an example of the program in operation:
| ?- b(4,A),format(&quot;~s &quot;,[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]