 #195
Parentheses... Again

 Difficulty: Medium Topics: math combinatorics

In a family of languages like Lisp, having balanced parentheses is a defining feature of the language. Luckily, Lisp has almost no syntax, except for these "delimiters" -- and that hardly qualifies as "syntax", at least in any useful computer programming sense.

It is not a difficult exercise to find all the combinations of well-formed parentheses if we only have N pairs to work with. For instance, if we only have 2 pairs, we only have two possible combinations: "()()" and "(())". Any other combination of length 4 is ill-formed. Can you see why?

Generate all possible combinations of well-formed parentheses of length `2n` (n pairs of parentheses). For this problem, we only consider '(' and ')', but the answer is similar if you work with only {} or only [].

There is an interesting pattern in the numbers! `(= [#{""} #{"()"} #{"()()" "(())"}] (map (fn [n] (__ n)) [0 1 2]))` `(= #{"((()))" "()()()" "()(())" "(())()" "(()())"} (__ 3))` `(= 16796 (count (__ 10)))` `(= (nth (sort (filter #(.contains ^String % "(()()()())") (__ 9))) 6) "(((()()()())(())))")` `(= (nth (sort (__ 12)) 5000) "(((((()()()()()))))(()))")`

Code which fills in the blank: