Generate Parentheses

A string of parentheses is well-formed when every ) closes a ( that came before it and nothing is left open — (()) and ()() are well-formed, but )( and (() are not. Given a number n, produce every well-formed string that uses exactly n pairs of parentheses. This is LeetCode 22; the number of answers for a given n is the Catalan number, which is why n = 3 has 5 results and the count climbs fast.

Signature

generateParentheses(n)  // integer n >= 0  ->  array of every well-formed string with n pairs

The order of the strings in the returned array is not specified — only the set of strings matters.

Examples

generateParentheses(1); // ['()']

generateParentheses(2); // ['(())', '()()']   (in any order)

generateParentheses(3);
// ['((()))', '(()())', '(())()', '()(())', '()()()']   (5 strings, any order)

Notes

• Well-formed — scanning left to right, the number of ) never exceeds the number of (, and the two counts are equal at the end. (() and ()) are both malformed.
• Order is not specified — return the strings in whatever order your algorithm produces; a grader compares the set, not the sequence.
• n = 0 — there is exactly one well-formed string using zero pairs: the empty string. generateParentheses(0) returns [''], not [].
• The count is a Catalan number — 1, 2, 5, 14, 42, … for n = 1, 2, 3, 4, 5. The result set grows roughly like 4^n, so keep n small.
• Every string has length 2n and uses only the two characters ( and ). No duplicates appear in the output.